21-09-2016, 03:56 PM
1455603450-Lowerbounds1.docx (Size: 18.18 KB / Downloads: 3)
By "lower bounds" here we mean a lower bound on the complexity of a problem, not an algorithm. Basically we need to prove that no algorithm, no matter how complicated or clever, can do better than our bound. This is often hard!
That is: we say that f(n) is a lower bound on the complexity of a problem P if, for every algorithm A to solve P, and every n, there exists some input I of size n such that A uses at least f(n) steps on input I.
Why do we care about lower bounds in an algorithms course? Because we want our algorithms to be fast, as fast as possible. If we can prove that no algorithm can be faster than one we have devised, then we can stop there, making no more efforts to improve.
Lower bound methods
Counting argument -- everything is eventually a “counting argument”. Usually tedious.
Incompressibility argument – for average case
Adversary argument -- for worst case.
Adversary arguments
Generally, we can think of a lower bound proof as a game between the algorithm and an "adversary". The adversary should be thought of as a very powerful, clever being that is trying to make your algorithm run as slowly as possible. The adversary cannot "read the algorithm's mind", but it can try to be prepared for anything the algorithm does. Finally, the adversary is not allowed to "cheat"; that is, the adversary cannot answer questions inconsistently.
The algorithm, of course, is trying to run as quickly as possible. The adversary is trying (through its cleverness) to force the algorithm to run slowly.
What is an Adversary?
Maybe considered as a second algorithm which intercepts access to data structures.
Constructs the input data only as needed
Attempts to make original algorithm work as hard as possible
Analyze Adversary to obtain lower bound.
Important Restriction
Although data is created dynamically, the adversary must return consistent results.
The adversary does not lie. If it replies that x[1]<x[2], we cannot have x[2]<x[1].
Example 1.
Oracle and adversary
Given some computational model, the oracle tells the outcome of each comparison. In order to derive a good lower bound, the oracle tries its best to cause the algorithm to work as hard as it might.
Take the example of a tournament where the values are called players and the largest value is interpreted as the winner and the second largest is taken as the runner up. So the problem is the similar to finding the largest and the second largest number out of a set of n numbers.
Second largest
Since we can’t determine the second largest element without having determined the largest element, at least n-1 comparisons are necessary. We need to show that there is always some sequence of comparisons which forces the second largest to be fund in (logn)-1 additional comparisons
Tournament theory
The winner of the tournament has played x matches then there are x people who are candidates for the runner up position. The runner up has lost only once to the winner and other x-1 persons must have lost to one other person. We can produce a oracle which decides the results of matches in such a way that winner plays logn other people.
In a match between a and b the oracle declares a as the winner if a is previously undefeated and b has lost at least once or if both a and b are undefeated but a has won more match then b. In any other case the oracle can decide arbitrarily as long as it remains consistent.