How to calculate the complexity of an algorithm?

Question

int sum = 0;
for (int n = N; n > 0; n /= 2)
    for(int i = 0; i < n; i++)
        sum++;


int sum = 0;
for (int i = 1 i < N; i *= 2)
    for (int j = 0; j < i; j++)
         sum++;

int sum = 0;
for (int i = 1 i < N; i *= 2)
    for (int j = 0; j < N; j++)
        sum++;

I have been suffering from this for a lot of time. I am still a second-year student but I still can't calculate the complexity of an algorithm. How can I calculate it? I feel very incompetent because I never seem to get it!

For example, is the complexity of a for loop always N? How to know? Can you recommend any resources I can read? Any videos?

Let's take first example: Think what you are doing with division for 1st example? Are you elimination half? What about second for loop? How many times it runs? — SMA, Dec 23 '18 at 15:35

Kenpachi Zaraki · Answer 1 · 2018-12-23T18:06:08.897

Well your first and second example is same (in terms of time complexity). For them, time complexity is O(N). Why is it. Let us compute. For the first example, your inner loop runs for N times, then N/2 times, then N/4 and goes upto 1. So, the time complexity is O(N+N/2+N/4+..+1) and sum of this GP is (2n-1). So, the time complexity for first case is O(N).

For the second example, your inner loop runs for 1 time, then 2 times, 4 times, and goes upto N. So, the time complexity is O(1+2+4+...+N) and sum of this GP is 2^log(N+1)-1 which is equal to N. So, the time complexity for the second case is also O(N).

For the third example, first loop runs for log(N) time and inner loop runs for N time and since each of them is independent, required time complexity is O(NlogN). (All calculations are approximate and all log bases are 2)

Well, to know about time complexity of a for loop, you have to see how many times "i" is assigned a value (can be same or different).

To learn about time complexity, check out hackerearth material and every time you write an algorithm, try to calculate its time complexity. Its the best method to learn it and check out Masters theorem for recurrence relation but know its basic too.

score 1 · Answer 2 · answered Dec 23 '18 at 15:40

1

Resource

https://www.geeksforgeeks.org/analysis-of-algorithms-set-4-analysis-of-loops/

Explanation

A general idea, Complexity of a loop means the number of times that will run. So a for loop for(int i=0;i<10;i++) is of Complexity O(n) where n=10. If there are multiple loops (not nested) the complexity of the code will be the highest n. If the loops are nested, like in the 3rd example you have shown above, the limit of both loop, which is N, gets multiplied. Making the complexity O(N square). (This is a general idea and not the precise definition!)

answered Dec 23 '18 at 15:40

javan.rajpopat

127
14

1

For third example, time complexity will be O(NlogN) not O(N^2) – Kenpachi Zaraki Dec 23 '18 at 18:12
1

@KenpachiZaraki yes sorry, I didn't notice i*=2, I gave the answer for i++ instead. – javan.rajpopat Dec 23 '18 at 19:53

AbsoluteSpace · Answer 3 · 2019-06-14T16:54:45.450

This previous question may be helpful because there are a few different approaches to calculate the complexity of an algorithm, and quite a few good resources.

As for your example, the complexity of a for loop may not always be N.

For example the following code snippet is linear (with a time complexity of N) because it goes from every iteration i = 0 to i = N sequentially,

for (int i = 0; i < N; i++) {
    sum++;
}

Whereas this code snippet is logarithmic in its time complexity because it doesn't progress sequentially through every value from 0 to N, but instead is multiplied by 2.

for (int i = 0; i < N; i*2) {
    sum++;
}

How to calculate the complexity of an algorithm?

3 Answers3