# how to prove the complexity of an algorithm mathematically

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?

• This isn't a subjective question in any way, and doesn't belong on programmers.se. Feb 7, 2011 at 18:29
• If you truly know something, then why ask a question?
– Job
Feb 7, 2011 at 18:32
• Might be appropriate for math.se or cstheory.se Oct 19, 2011 at 17:06

## 6 Answers

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:

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

• Big O is a measure of the time an algorithm takes (time complexity). I assume this is what Sarath means by complexity. Feb 7, 2011 at 18:08
• Big O is a measurement of the relative scalability of the algorithm as a function of the input size. O(n^3) scales with a factor 8 when n doubles.
– user1249
Feb 7, 2011 at 18:13
• @Thorbjørn, not strictly true. Big-O is an upper bound: Big-theta is a tight bound. Feb 7, 2011 at 18:36
• @Peter, ok, forgot to write "worst case".
– user1249
Feb 7, 2011 at 18:42
• @rreeverb: Big Oh is also commonly used to describe memory usage for an algorithm. Hence I used computing resources because time and memory are common limits to a machines capability. Feb 7, 2011 at 19:23

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"?)

• I think you have to agree beforehand on a set of operations that make sense. E.g. +, -, *, /, and function application. Feb 7, 2011 at 17:46
• "What counts as an operation" depends on the context. There was an interesting question recently on one of the SE sites about bubble sort being faster than quicksort when sorting on a tape, because then the cost of accessing an arbitrary element of the array isn't constant but depends on the position relative to the tape head - so the partition step of quicksort went from being O(n) to O(n^2). Feb 7, 2011 at 18:35

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.

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:

An = A1rn-1 which leads to

1 = A1(1/2)n-1

It gets easier after this: Divide both sides by A1, Multiply by Log 2 and solve for N!

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

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.