## Time complexity 2 – how to count it

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 comlexity of your algorithm you should always define a simple computer model.

My model looks like this:

- single processor with sequential execution
- 1 unit of time for : arithmetical operations, logical operations, assigment, return
- single processor, 32bit

I am using C# code for ilustration, but what am I going to show you apply for all programming languages.

You can download demo code here.

**Example 1 – Constant **

Code:

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**

Code:

private static int Total(int[] arr) { var total = 0; for (int i = 0; i < arr.Length; i++) { total += arr[i]; } return total; }

Time analysis

First column is a how much unit of time 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 **assigment** and we defined that it will take 1 unit.

**For cycle** will take 3 unit of time, because there is **assigment** to variable i, **condition** and **incrementation** of variable i

Second column is a 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 **assigment** and **sum** => **2 units**

and it will be **executed n times** => **2(n)**

Third column is a equation for this particular algorithm.

1 + 3n +1 +2n +1 = 5n +3

1(total variable assigment) + 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 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 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 lenght = 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 equatuon will always match the number of operations.

Don’t forget that for quadratic equation you have to use matrix that has 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 tell us aproximately what function our algorithm will copy. I will talk more about big-oh in my next post.