The Question
How to find time complexity of an algorithm?
What have I done before posting a question on SO ?
I have gone through this, this and many other links
But no where I was able to find a clear and straight forward explanation for how to calculate time complexity.
What do I know ?
Say for a code as simple as the one below:
char h = 'y'; // This will be executed 1 time
int abc = 0; // This will be executed 1 time
Say for a loop like the one below:
for (int i = 0; i < N; i++) {
Console.Write('Hello World !');
}
int i=0; This will be executed only once.
The time is actually calculated to i=0
and not the declaration.
i < N; This will be executed N+1 times
i++ ; This will be executed N times
So the number of operations required by this loop are
{1+(N+1)+N} = 2N+2
Note: This still may be wrong, as I am not confident about my understanding on calculating time complexity
What I want to know ?
Ok, so these small basic calculations I think I know, but in most cases I have seen the time complexity as
O(N), O(n2), O(log n), O(n!).... and many other,
Can anyone help me understand how does one calculate time complexity of an algorithm? I am sure there are plenty of newbies like me wanting to know this.
When you're analyzing code, you have to analyse it line by line, counting every operation/recognizing time complexity, in the end, you have to sum it to get whole picture.
For example, you can have one simple loop with linear complexity, but later in that same program you can have a triple loop that has cubic complexity, so your program will have cubic complexity. Function order of growth comes into play right here.
Let's look at what are possibilities for time complexity of an algorithm, you can see order of growth I mentioned above:
Constant time has an order of growth
1
, for example:a = b + c
.Logarithmic time has an order of growth
LogN
, it usually occurs when you're dividing something in half (binary search, trees, even loops), or multiplying something in same way.Linear, order of growth is
N
, for exampleLinearithmic, order of growth is
n*logN
, usually occurs in divide and conquer algorithms.Cubic, order of growth
N^3
, classic example is a triple loop where you check all triplets:Exponential, order of growth
2^N
, usually occurs when you do exhaustive search, for example check subsets of some set.I know this question goes a way back and there are some excellent answers here, nonetheless I wanted to share another bit for the mathematically-minded people that will stumble in this post. The Master theorem is another usefull thing to know when studying complexity. I didn't see it mentioned in the other answers.
O(n) is big O notation used for writing time complexity of an algorithm. When you add up the number of executions in an algoritm you'll get an expression in result like 2N+2, in this expression N is the dominating term(the term having largest effect on expression if its value increases or decreases). Now O(N) is the time comlexity while N is dominating term. Example
here total number of executions for inner loop are n+1 and total number of executions for outer loop are n(n+1)/2, so total number of executions for whole algorithm are n+1+n(n+1/2) = (n^2+3n)/2. here n^2 is the dominating term so the time complexity for this algorithm is O(n^2)
This is an excellent article : http://www.daniweb.com/software-development/computer-science/threads/13488/time-complexity-of-algorithm
The below answer is copied from above (in case the excellent link goes bust)
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 ( ) where 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. ;)
You add up how many machine instructions it will execute as a function of the size of its input, and then simplify the expression to the largest (when N is very large) term and can include any simplifying constant factor.
For example, lets see how we simplify
2N + 2
machine instructions to describe this as justO(N)
.Why do we remove the two
2
s ?We are interested in the performance of the algorithm as N becomes large.
Consider the two terms 2N and 2.
What is the relative influence of these two terms as N becomes large? Suppose N is a million.
Then the first term is 2 million and the second term is only 2.
For this reason, we drop all but the largest terms for large N.
So, now we have gone from
2N + 2
to2N
.Traditionally, we are only interested in performance up to constant factors.
This means that we don't really care if there is some constant multiple of difference in performance when N is large. The unit of 2N is not well-defined in the first place anyway. So we can multiply or divide by a constant factor to get to the simplest expression.
So
2N
becomes justN
.Loosely speaking, time complexity is a way of summarising how the number of operations or run-time of an algorithm grows as the input size increases.
Like most things in life, a cocktail party can help us understand.
O(N)
When you arrive at the party, you have to shake everyone's hand (do an operation on every item). As the number of attendees
N
increases, the time/work it will take you to shake everyone's hand increases asO(N)
.Why
O(N)
and notcN
?There's variation in the amount of time it takes to shake hands with people. You could average this out and capture it in a constant
c
. But the fundamental operation here --- shaking hands with everyone --- would always be proportional toO(N)
, no matter whatc
was. When debating whether we should go to a cocktail party, we're often more interested in the fact that we'll have to meet everyone than in the minute details of what those meetings look like.O(N^2)
The host of the cocktail party wants you to play a silly game where everyone meets everyone else. Therefore, you must meet
N-1
other people and, because the next person has already met you, they must meetN-2
people, and so on. The sum of this series isx^2/2+x/2
. As the number of attendees grows, thex^2
term gets big fast, so we just drop everything else.O(N^3)
You have to meet everyone else and, during each meeting, you must talk about everyone else in the room.
O(1)
The host wants to announce something. They ding a wineglass and speak loudly. Everyone hears them. It turns out it doesn't matter how many attendees there are, this operation always takes the same amount of time.
O(log N)
The host has laid everyone out at the table in alphabetical order. Where is Dan? You reason that he must be somewhere between Adam and Mandy (certainly not between Mandy and Zach!). Given that, is he between George and Mandy? No. He must be between Adam and Fred, and between Cindy and Fred. And so on... we can efficiently locate Dan by looking at half the set and then half of that set. Ultimately, we look at O(log_2 N) individuals.
O(N log N)
You could find where to sit down at the table using the algorithm above. If a large number of people came to the table, one at a time, and all did this, that would take O(N log N) time. This turns out to be how long it takes to sort any collection of items when they must be compared.
Best/Worst Case
You arrive at the party and need to find Inigo - how long will it take? It depends on when you arrive. If everyone is milling around you've hit the worst-case: it will take
O(N)
time. However, if everyone is sitting down at the table, it will take onlyO(log N)
time. Or maybe you can leverage the host's wineglass-shouting power and it will take onlyO(1)
time.Assuming the host is unavailable, we can say that the Inigo-finding algorithm has a lower-bound of
O(log N)
and an upper-bound ofO(N)
, depending on the state of the party when you arrive.Space & Communication
The same ideas can be applied to understanding how algorithms use space or communication.
Knuth has written a nice paper about the former entitled "The Complexity of Songs".