how to prove the complexity of an algorithm mathematically

Question

I know the fundamental algorithms and it's complexities. for e.g if Binary Search has Complexity O(log n), then how I can mathematically prove this?

Answer 1

I assume you're asking about how to measure algorithm time complexity with regards to its input (how the algorithm time grows as N grows). One way is to model the algorithm in the form of a recurrence equation and then solve via a number of techniques. Common techniques are master theorem, substitution, recurrence trees, ...

The binary search algorithm can be seen as recurrences of dividing N in half with a comparison. So T(n) = T(n/2) + 1. Solve this by the master theorem to show the function is log n.

For a complete overview of this type of stuff I suggest working through these two classes:

http://aduni.org/courses/discrete and http://aduni.org/courses/algorithms

Answer 2

Big Oh isn't really a description of algorithm complexity, as in how many decisions and branches are made, Big Oh is a description or measure of computing resources used by an algorithm.

Anyways you'll have to become familiar with all the complicated math behind complexity theory, learn about P, NP, EXPTIME complextity classes, and all that fun stuff.

http://en.wikipedia.org/wiki/Computational_complexity_theory

Answer 3

Informally, you would use an argument such as: let f(n) be the number of operations needed to perform a binary search on n elements. Then first argue that the relationship

f(n) = 2 f(n/2) + c

holds, and then use the Master Theorem.

Formally "proving" complexity is something that has always bothered me, since this area of theory seems (at least as presented in introductory computer science) to be trying to apply formal mathematics to a vague, informal foundation. (For instance, what exactly counts as an "operation"?)

Answer 4

For an introduction to data structures and algorithms, Cormen & al Introduction to Algorithms is really great.

As for the specific case of computing complexities, it is generally a matter of expressing it as a recursive relation, then proving that relation is true, then reducing this recursive relation to a more manageable formula.

The Master Theorem comes handy in the latter step, read the wikipedia article, it should be sufficient for your simple example.

Answer 5

For Binary Search Only!

Here is my way of doing it:

To implement binary search on a sorted list that contains N elements, we keep dividing the list in halves until we 'corner' the key. This tells us that the problem size decreases by half, [Eg. 100 : 50 : 25 : 12 : 6 : 3 : 1], until it reaches (worst case) 1!

This gives us Geometric progression with a Common ratio = 1/2 and the Nth term being 1.

GP formula is:

A_n = A₁r^n-1 which leads to

1 = A₁(1/2)^n-1

It gets easier after this: Divide both sides by A₁, Multiply by Log ₂ and solve for N!

Should give you the number of steps to reach A_n which is Log ₂^A1 + 1 which in turn is O(log n)

Answer 6

There are mathematical techniques to prove big-oh. IIRC there where some difference equations involved. Any decent textbook on the topic should be able to teach you the ropes.