upper bound, lower bound

algorithm complexity-theory time-complexity
DarthVader picture DarthVader · Nov 30, 2009 · Viewed 37.1k times · Source

What does it mean to prove an upper bound or lower bound to an algorithm?

Answer

caf picture caf · Nov 30, 2009

Proving an upper bound means you have proven that the algorithm will use no more than some limit on a resource.

Proving a lower bound means you have proven that the algorithm will use no less than some limit on a resource.

"Resource" in this context could be time, memory, bandwidth, or something else.

Related questions

How to find time complexity of an algorithm

The Question How to find time complexity of an algorithm? What have I done before posting a question on SO ? I have gone through this, this and many other links But no where I was able to find a clear …

Read More
What is a plain English explanation of "Big O" notation?

I'd prefer as little formal definition as possible and simple mathematics.

Read More
What would cause an algorithm to have O(log log n) complexity?

This earlier question addresses some of the factors that might cause an algorithm to have O(log n) complexity. What would cause an algorithm to have time complexity O(log log n)?

Read More