Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I've not gone much deep into CS. So, please forgive me if the question is not good or out of scope for this site.

I've seen in many sites and books, the big-O notations like $O(n)$ which tell the time taken by an algorithm. I've read a few articles about it, but I'm still not able to understand how do you calculate it for a given algorithm.

share|improve this question
    
I think there is no one way that would help you calculate the time complexity of any algorithm. –  svick Mar 10 '12 at 12:38
    
I have tried to extrapolate your needs from what you wrote; please add a clear question. –  Raphael Mar 10 '12 at 12:51
4  
I think this question is too broad: the answer would essentially be a few lectures' worth of information. –  Alex ten Brink Mar 10 '12 at 14:37
    
Aslo see Are runtime bounds in P decidable? –  Kaveh Mar 10 '12 at 15:23
    
There is no general algorithmic way to computable the running time of a given machine (even in the case we already know that it is a polynomial time machine). It might help if you restate the question to be about the techniques people use in analyzing the (worst-case) time-complexity of a given algorithm in practice (or in undergraduate algorithms course assignments). –  Kaveh Mar 10 '12 at 15:25

5 Answers 5

This part of computer science is called analysis of algorithms. Many times people are satisfied when they are given a guarantee that an algorithm’s performance is not worse than a specified bound and they dont’t care about the exact performance.

This bound is conveniently denoted with the Landau-notation (or big-Oh notation) and in case of $\mathcal{O}(f(n))$ it is an upper bound. That is for inputs of size $n$ the algorithms complexity is guaranteed not to exceed (a constant times) $f(n)$. Most of the time it is clear from the context what the “unit” this bound is measured in is. Note that “runtime” measured in actual time units (seconds, minutes, etc.) is frowned upon as you can’t compare them meaningful across different computers. Typically a “costly” elementary operation is identified, like compares and exchanges in sorting algorithms, or pushs and pops if the algorithm includes a stack, or updates to a tree data structure used in the algorithm. This elementary operation is understood as to be the dominating one, that has the largest contribution to the algorithm’s complexity, or perhaps it is more expensive than another one in a particular setting (multiplications are considered to be more expensive then additions for example). It has to be selected so that the cost of other operations are (at most) proportional to the number of the elementary operations.

This upper bound is called the worst-case bound or the worst-case complexity of the algorithm. Because it has to hold for all inputs of the same size $n$ and the worst-case inputs incur the highest (worst) cost. The actual performance for a specific input of size $n$ may be a lot lower than this upper bound.

While it is possible to do an exact analysis it is usually much more involved to arrive at an exact result. Also, an exact analysis means accounting for all operations in the algorithm, and that requires a rather detailed implementation; while counting elementary operations can be done from a mere sketch of the algorithm most of the time. It is nice if such an analysis is possible but it is not always necessary. Because small inputs are not much of a problem, you want to learn what happens when the input size $n$ gets large. Knowing that the algorithm’s complexity is bounded by $5n^2+3n-2\log(n)$ is nice but overkill when looking at the performance asymptotically ($n\rightarrow \infty$), because the term $n^2$ dominates the others for large $n$. So proving an upper bound of $\mathcal{O}(n^2)$ suffices.

If you have two algorithms and you can guarantee that one performs like $\Theta(n^2)$ and the other like $\Theta(n)$ you can easily decide which one is “faster”, has a lower “cost”, uses less elementary operations, just by noting that a quadratic function grows faster than a linear function. In practice that means that the linear algorithm finishes earlier or that it can process larger inputs in the same time. But it might be that the constants hidden by $\Theta$ are such that for practical $n$ the $\Theta(n^2)$ algorithm is faster.

However if you have three algorithms all with a $\mathcal{O}(n^3)$ guarantee on their complexity you are hard pressed when you have to decide which algorithm to choose. Then more detailed bounds are needed, or perhaps even an exact analysis.

It may very well be that this analysis is hard to do and you can’t give a tight bound. Then there is a gap between the actual worst-case performance, perhaps $n^2$ and your bound of perhaps $\mathcal{O}(n^3)$. Then a clever idea, a more involved analysis is necessary to close the gap and provide an improved bound. This is just an improvement of the bound not to the algorithm. Typically you have to argue more carefully when you want to prove a tighter bound.

This all said, an analysis of an algorithm can be as simple as looking at the implementation and counting the nesting depth of the for loops to conclude that the operations in the innermost loop are executed not more than $\mathcal{O}(n^3)$ times when say three loops are nested.

For some types of algorithms the analysis follows always the same pattern, so there is a theorem like the master theorem, that tells you generically what the algorithms performance will be. Then you only have to apply the theorem to get the bound.

Perhaps you are faced with a recursive algorithm and you are able to describe the algorithms complexity by a recurrence relation. Then solving the recurrence gives the desired bound.

Typically you have to exploit some properties of the inputs. Sorting algorithms are deeply connected to permutations and knowing something about the number of inversions in a permutation helps a lot when analysing the performance.

There is no general approach on how to proceed in an analysis. As discussed above it depends on the algorithm, its inputs, its implementation, the elementary operation choosen, what mathematical tools you have at hands, the desired sharpness of the bound.

Some may prefer a smoothed-analysis or an average-case analysis over a treatment of the worst-case. Then different techniques are necessary.

share|improve this answer
    
In your fifth paragraph, you mean $\Theta$, don't you? Using only $\cal{O}$ you can not immediately read of the (asymptotically) better algorithm; maybe one analysis is simply to coarse. This common fallacy alone is well worth pointing out. –  Raphael Mar 10 '12 at 13:47
1  
@Raphael Of course, the unfortunate sloppiness that creeps in when using the big-Oh notation. Good catch. –  uli Mar 10 '12 at 13:55

Big O notation ($\mathcal{O}$) ignores all constant factors so that you're left with an upper bound on growth rate.

For a single line statement like assignment, where the running time is independent of the input size $n$, the time complexity would be $\mathcal{O}(1)$:

int index = 5;  *//constant time*   
int item = list[index]; *//constant time*

For a loop like:

for i:=1 to n do  
  x:=x+1;

The running time would be $\mathcal{O}(n)$, because the line $x=x+1$ will be executed $n$ times.

But for:

for ( i = 0; i < N; i++ ) {  
  for ( j = 0; j < N; j++ )  
    statement; 
}

It'd be $\mathcal{O}(n^2)$ because the statement will be executed $n$ times for every $i$.

For a while statement, it depends on the condition and the statement which will be executed in it.

i := 1;
while ( i < n )  
  i = i * 2;

The running time is logarithmic, $\mathcal{O}(\log n)$ because of the multiplication by 2.

For instance:

Double test(int n){  
  int sum=0;  -> 1 time
  int i;  -> 0 time
  for(i=0; i<=n;i++)  -> n+2 times
  {
    scanf("%d",&a);  -> n+1 times
    sum=sum+a;  -> n+1 times
  }
  return sum;  -> 1 time
}

Which is $3n+6$. Hence, $\mathcal{O}(n)$.

For more information, have a look at this Wikipedia atricle: time complexity

share|improve this answer

A statement like "Algorithm $A$ takes $\cal{O}(n)$ time." does not say much about the actual runtime of the algorithm on a given instance. You (usually) have to read it like this:

"For a fixed $n_0 \in \mathbb{N}$ and for all $n \geq n_0$ the runtime of $A$ on a worst-case instance of size $n$ is bounded from above by a function $f(n) = cn$ with $c \in \mathbb{R}$ fixed."

This is called "asymptotic runtime bounded by $\cal{O}(n)$", a much weaker statement.

  • First of all, it does not tell you anything for "small" instances; it might even be the case that $n_0$ is so large that you will only ever encounter instances you have no runtime bound for.
  • $c$ can be arbitrarily large. Combined with the first item, asymptotically slower algorithms might outperform a faster one on all relevant instances.
  • A bound given by $\cal{O}$ is not necessarily sharp. For instance, all polynomial algorithms have runtime in $\cal{O}(2^n)$; therefore, such a bound might not characterise the algorithm well at all.
  • In most cases, only worst-case instances are considered. Often, this is not very representative for the real behaviour of the algorithm. Prominent examples include Quicksort and Simplex algorithm.

All of these items come up because sharper analysis is hard or even impossibly to perform without knowledge about the concrete machine an algorithm is run on. Aside from determining $c$ precisely, deriving $\Theta$-classes (both upper and lower bound), average case analysis, amortised analysis and smoothed analysis are popular techniques to better describe an algorithm's behaviour.

Note furthermore tha memory hierarchies are usually ignored even though they can heavily influence performance. See my answer here for a quick explanation of the different Landau symbols.

That said, analysing an algorithm is conceptually simple: Count all executed operations and sum up their (relative) runtimes. As this is often (too) hard, some tricks are employed; the desired quality of the resulting bounds inform which one to employ to which extent. Performing a good analysis (i.e. one that yields exactly the desired precision) is definitely an art.

  • Consider only best- or worst-case instances (often implicitly), or take the average over all instances.
  • Count only those kinds of operations that dominate runtime, i.e. that occur (asymptotically) most often. Form example, analyses of sorting algorithms often count only element comparisons, which is not always appropriate; determining which operation dominates takes experience. Note that restricting yourself like this will effectively prevent you from obtaining any amount of precision regarding runtime estimations.
  • Apply general calculation rules. For instance, loops translate to sums and recursive algorithms to recurrence equations.
  • Simplify your model, e.g. count all elementary operations with a unit cost and ignore pipelines, memory IO peculiarities and caches.

If you want to see exceptionally rigorous analyses, take a peek into Donald Knuth's "The Art of Computer Programming". For examples with a more common resolution try Cormen, Leiserson et al, "Introduction to Algorithms".

share|improve this answer

Let me give a graphical representation. Consider two functions $f(n)$ and $g(n)$ that looks something like below:

normal

When you say a function $f(n)$ is bound by $\mathcal{O}(g(n))$ i.e. ($f(n)=\mathcal{O}(g(n))$) what you actually mean is there exists a constant $c$ and $n_0$ such that $f(n)\geq c*g(n)$, $\forall n\geq n_0$ like the figure below: enter image description here

Likewise, when you say a function $f(n)$ is bound by $\Omega (g(n))$ i.e. ($f(n)=\Omega (g(n))$) what you actually mean is there exists a constant $c$ and $n_0$ such that $f(n)\leq c*g(n)$, $\forall n\geq n_0$ like the figure below:

enter image description here

In the same manner, when you say a function $f(n)$ is bound by $\Theta (g(n))$ i.e. ($f(n)=\Theta (g(n))$) what you actually mean is there exists a two constants $c_1$ and $c_2$ for the SAME FUNCTION and $n_0$ and $n_1$ such that $c_1*g(n)\leq f(n) \leq c_2*g(n)$, $\forall n\geq n_0,n_1$ like the figure below:

enter image description here

NOTE: You can remember these notations as - $O$: when you write $O$ you always end up finishing at the top so the line is above, $\Omega$: When you write the notation, you always finish it at the bottom so the line is below the function and $\Theta$: the line is in the middle.

Now, having said this and you have a basic understanding of all asymptotic notations, look at the following figure from here. The following figure dices up the analysis of runtime of the merge sort algorithm:

enter image description here

share|improve this answer
2  
This answer does not talk about algorithm analysis at all; maybe move it to this question? –  Raphael Mar 10 '12 at 15:54
    
@Raphael The OP said he doesn't have a much deeper understanding of algorithm complexity which is why I chose to explain it this way instead of going to seep into the complexity analysis and yeah, this answer also suits well to the other question. Should I repost it there? –  Sunil Mar 10 '12 at 16:09
    
Landau symbols are not exclusive to algorithm analysis, and algorithm analysis does not necesarily use Landau symbols. Therefore, I don't think an answer that talks solely about Landau symbols is no good. My suggestion would be to remove the answer here and repost on the question I linked; it can be useful there. –  Raphael Mar 10 '12 at 16:42
    
@Raphael If the OP doesn't find it useful, I will delete the post. Cheers. –  Sunil Mar 10 '12 at 16:48

$\cal{O}$, $\Theta$ and $\Omega$ all denote some sort of expression, with it's constant factors stripped off. The difference is that the O notation sets an upper bound on the algorithm's running time, the Omega notation sets a lower bound, and the Theta notation "sandwiches" the algorithm's running time.

To calculate the running time of an algorithm, you have to find out what dominates the running time. For example, if you've designed an algorithm which does binary search and quick sort once, it's running time is dominated by quick sort.

But you'll finally have to calculate the running time of an algorithm which doesn't (at least partially) consist of algorithms which you have seen before. In this case, you have to find the part that spends the most time. It usually means that you have to look at loops, nested loops and recursive calls.

There is much more to say on algorithm analysis and there are also other techniques, like amortized analysis. To find out more, I highly recommend you to read "Introduction to Algorithms", Third Edition, CLRS.

share|improve this answer

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.