-1

I am practicing time complexity and some of them if a bit too complicated for me. I would really appreciate of someone could explain these for me.

A) The time complexity is O(n). How is that?

for (int i = N; i > 0; i = i/2) {
    for (int j = i+i; j > 0; j--) {
         doSomething(i, j);
    }
}

B) The time complexity is O(n logn). How is that?

for (int i = N+N; i > 0; i--) {
    for (int j = N; j > 0; j = j/2) {
        doSomething(i, j);
    }
}
Emsko
  • 85
  • 12
  • 1
    Does this answer your question? [How to find time complexity of an algorithm](https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm) – Welbog May 04 '21 at 13:57
  • I have been practicing time complexity with many different examples. This is a very good link but I still had a hard time getting my head around these two algorithms. But thank you anyway – Emsko May 05 '21 at 10:46

2 Answers2

1

I suppose we must assume that the execution of doSomething takes constant time, independent of the values it gets as arguments.

Algorithm A:

On the first iteration of the outer loop, the inner loop iterates 2 times. Every next iteration of the outer loop, the number of iterations of the inner loop is halved. So we get this series:

      2 + + /2 + /4 + /8 + ... + 2

Given that this series is finite, but has the pattern of 1/2 + 1/4 + 1/8 + 1/16 + ..., we can conclude that this is less than 4, and so it is O().

Algorithm B:

Here the number of iterations of the inner loop does not depend on the value of , so it is always the same: each time it performs log2 iterations (since is halved each iteration). As the outer loop iterates 2 times, doSomething is called 2log2, which is O(log)

trincot
  • 317,000
  • 35
  • 244
  • 286
-1

problem A

Here the first loop will execute log2(n)+1 times, and the second loop will execute i+i times. So what will the value of i in every second loop.

for n, it will be like

n + n/2 + n/4 + n/8 + n/16 + .......

summation of this will be the answer.

as we know a + ar + ar^2 + ar^3 + ar^4 .... + ar^m = (1-a^(m+1))/(1-a)

here a = n, r = 1/2 and m = log2(n)+1

n + n/2 + n/4 + n/8 + ... n/(2^(m)) =2n−n/2^m = 2n-1;

so the complexity is O(2n-1) = O(n)

problem B

here the first loop will execute n times. And for every first loop execution, the second loop will be executed log2(n)+1 time.

for (int j = n; j > 0; j = j/2)

for example n = 10 , value of j will be 10, 5, 2, 1 ,0. For 10 it will execute 4 times or log2(10)+1 times .

so for every first loop it will execute log2(n)+1 times. so the complexity is O(n(log2(n)+1)) = O (nlog(n))

Yead
  • 91
  • 5