Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
1  
This isn't a subjective question in any way, and doesn't belong on programmers.se. –  David Thornley Feb 7 '11 at 18:29
    
If you truly know something, then why ask a question? –  Job Feb 7 '11 at 18:32
    
Might be appropriate for math.se or cstheory.se –  Daenyth Oct 19 '11 at 17:06
add comment

6 Answers 6

up vote 2 down vote accepted

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

share|improve this answer
add comment

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

share|improve this answer
1  
Big O is a measure of the time an algorithm takes (time complexity). I assume this is what Sarath means by complexity. –  rreeverb Feb 7 '11 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 '11 at 18:13
1  
@Thorbjørn, not strictly true. Big-O is an upper bound: Big-theta is a tight bound. –  Peter Taylor Feb 7 '11 at 18:36
    
@Peter, ok, forgot to write "worst case". –  user1249 Feb 7 '11 at 18:42
2  
@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. –  whatsisname Feb 7 '11 at 19:23
add comment

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

share|improve this answer
    
I think you have to agree beforehand on a set of operations that make sense. E.g. +, -, *, /, and function application. –  Andres F. Feb 7 '11 at 17:46
1  
"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). –  Peter Taylor Feb 7 '11 at 18:35
add comment

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.

share|improve this answer
add comment

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)

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.