In my last post, I was writing about time complexity and how important it is to think about it when you are writing your code.
Today I would like to show you some more examples how to compute time complexity of algorithm.
When you are trying to solve time complexity of your algorithm, you should always define a simple computer model.
My model looks like this:
Specifications
- Single processor with sequential execution
- 1 unit of time for : arithmetical operations, logical operations, assignment, return
- Single processor, 32bit
I am using C# code for illustration, but what am I going to show you applies to all programming languages.
You can download the demo code here.
Example 1 – Constant
The code is as follows:
private static int Add(int a, int b)
{
return a + b;
}
Time analysis:
This is a constant time algorithm. In our model computer, it will take 2 units of time to finish. 1 unit for sum, another one for return statement.
Example 2 – Linear
The code is as follows:
private static int Total(int[] arr)
{
var total = 0;
for (int i = 0; i < arr.Length; i++)
{
total += arr[i];
}
return total;
}
Time analysis is as given below:
First column is a how many units of time it will take to our computer model to process this line of code.
var total = 0 will be 1 unit, because there is only assignment and we defined that it will take 1 unit.
For cycle will take 3 unit of time, because there is assignment to variable i, condition and incrementation of variable i.
Second column is how many times this piece of code will be executed. Variable n = arr.Length.
So for cycle will be executed n times (arr.Length) and it will take 3 units of time + 1 extra for false condition at the end. => 3(n) +1
total += arr[i] is assignment and sum => 2 units
and it will be executed n times => 2(n)
Third column is an equation for this particular algorithm:
1 + 3n +1 +2n +1 = 5n +3
1(total variable assignment) + 3n+1(for cycle) + 2n(add to total variable) + 1(return)
Time taken by this algorithm is linear.
Example 3 – Quadratic
Here we have 2 for cycles, one inside another one.
For simplicity, we have a matrix that has the same width(n) as height(m). Or you could say same number of columns(n) as rows(m). That means m=n and we don’t have to differentiate between them.
First for cycle is the same like example 2.
Second for cycle is different because it will be executed n-times, because it is inside for cycle that has size of n. => n(3(n)+1)
And also everything that is inside second for cycle will be executed n-times. => n(2(n))
When we solve the equation, the result is: 3 + 4n + 5n^2
Time taken by this algorithm is quadratic.
Details
My demo contains methods that have detail suffix like TotalDetail. These methods are the same like the methods without suffix however these methods count total units of time. With this functionality, you can check your equation result.
So for example, our linear example has equation: 5n + 3.
And we know that n = array length. For array length = 10, the number of operations must equal 5 * 10 + 3 = 53 units of time.
If you try the demo with different numbers, the result of equation will always match the number of operations.
Don’t forget that for quadratic equation, you have to use matrix that has the same number of columns as rows!
For example: n = m = 3.
Result will be: 3 + 4*3 + 5*(3)^2 = 3 + 12 + 45 = 60 units of time.
Summary
Growth of these methods are:
- Constant: 2 => O(1)
- Linear: 5n + 3 => O(n)
- Quadratic: 3 + 4n + 5n^2 => O(n^2)
I mentioned O in my last post, it is called big-oh and it basically tells us approximately what function our algorithm will copy. I will talk more about big-oh in my next post.
