How to come up with the runtime of algorithms? [duplicate]

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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".

Answer 4

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

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 \gt 0$ and $n_0$ such that $f(n)\leq c\cdot g(n)$, $\forall n\geq n_0$ like the figure below:

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 \gt 0$ and $n_0$ such that $f(n) \geq c\cdot g(n)$, $\forall n\geq n_0$ like the figure below:

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 \gt 0 $ and $c_2 \gt 0$ for the SAME FUNCTION and $n_0$ and $n_1$ such that $c_1\cdot g(n)\leq f(n) \leq c_2\cdot g(n)$, $\forall n\geq n_0,n_1$ like the figure below:

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:

Answer 5

$\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.