How to calculate time complexity of any algorithm or program ....
need help on this..

>How to calculate time complexity of any algorithm or program ....
The most common metric for calculating time complexity is Big O notation. This removes all constant factors so that the running time can be estimated in relation to N as N approaches infinity. In general you can think of it like this:
Is constant. The running time of the statement will not change in relation to N.
Is linear. The running time of the loop is directly proportional to N. When N doubles, so does the running time.
Is quadratic. The running time of the two loops is proportional to the square of N. When N doubles, the running time increases by N * N.
Is logarithmic. The running time of the algorithm is proportional to the number of times N can be divided by 2. This is because the algorithm divides the working area in half with each iteration.
Is N * log ( N ). The running time consists of N loops (iterative or recursive) that are logarithmic, thus the algorithm is a combination of linear and logarithmic.

In general, doing something with every item in one dimension is linear, doing something with every item in two dimensions is quadratic, and dividing the working area in half is logarithmic. There are other Big O measures such as cubic, exponential, and square root, but they're not nearly as common. Big O notation is described as O ( <type> ) where <type> is the measure. The quicksort algorithm would be described as O ( N * log ( N ) ).

Note that none of this has taken into account best, average, and worst case measures. Each would have its own Big O notation. Also note that this is a VERY simplistic explanation. Big O is the most common, but it's also more complex that I've shown. There are also other notations such as big omega, little o, and big theta. You probably won't encounter them outside of an algorithm analysis course.

Big Oh denotes "fewer than or the same as" <expression> iterations.
Big Omega denotes "more than or the same as" <expression> iterations.
Big Theta denotes "the same as" <expression> iterations.
Little Oh denotes "fewer than" <expression> iterations.
Little Omega denotes "more than" <expression> iterations.

Thanks for the lovely explanation Narue. I have a couple of questions though.

I assume that when you said the complexity for the following code was O(N log (N)), you meant the average case measure?


If I had to calculate the best and worst, how would I do that?

I tried to do best, and correct me if I'm wrong but that would be when the list has 1 element, so the best case scenario would be O(1)?

>I assume that when you said the complexity for the following code was
>O(N log (N)), you meant the average case measure?
Correct. Average and best case complexities are easier to figure out than worst case.

>If I had to calculate the best and worst, how would I do that?
To calculate the best case, simply assume a perfect partition right down the middle each time. This will roughly halve the data set and the time complexity is O(Nlog N), just like the average case, except it's a tighter bound, so while Big O is correct, you can use Big Theta to be more correct.

To calculate the worst case, assume the worst possible partition, which would basically be the left or rightmost item, so one half contains a single element and the other half contains everything else. It's fairly easy to see that this is linear, so the worst case time complexity is O(N).

>I tried to do best, and correct me if I'm wrong but that would be when
>the list has 1 element, so the best case scenario would be O(1)?
You could say that, but Big O notation doesn't assume the number of elements. It's a measurement of growth as the data set gets larger. So O(1) means that if you double the number of elements, the time the algorithm takes is the same. O(N) means that if the number of elements doubles, so does the time the algorithm takes to process them.

Thanks for that narue.

One more question. I have understood how to calculate the O of a simple algorithm but does that O depend upon the size of N as well? I read in an online book somewhere that O will have two values for the same algorithm, one when N was very large and another when N is small. Is that correct? If so, how do I calculate the value of say,

"3 n^2 - 100 n + 6" for a very small n?

I know the complexity for the above will be O(n^2) for very large n but what about very small n?

O notation removes all constants so that you're left with the largest growth rate, which will be dominant as N increases. Naturally, when N is small, the constants will be the dominant factor, so it can make sense to keep them in the equation rather than removing them if N is guaranteed to be small.

>I know the complexity for the above will be O(n^2) for very large n but what about very small n?
It will still be O(n^2), but if n is 5, for example, 100n totally dominates the algorithm as opposed to if n is 5000, where n^2 dominates.

That's what I thought but this page says different, rather the figures on the page say different. It's got me confused.

>rather the figures on the page say different
No, they say exactly the same thing. O notation is an upper bound, not a tight bound. And without assuming the size of N, the constants are irrelevant.

But theta is a tight bound right? So why does the theta of the same equation vary?

Sorry but I'm new to this and I think it's all in the english. My english isn't that great, one big reason why I'm having problems.