Trying to understand the reason for this time complexity

Question

I am trying to calculate the time complexity of these two algorithms. The book I am referring to specifies these time complexities of each.

A) Algorithm A: O(nlogn)

int i = n;
while (i > 0) 
{
  for (int j = 0; j < n; j++)
    System.out.println("*");
  i = i / 2;
}

B) Algorithm B: O(n)

while (n > 0) 
{
  for (int j = 0; j < n; j++)
    System.out.println("*");
  n = n / 2;
}

I can see how algo. A is O(nlogn). The for loop is O(n) and while loop is O(logn). However I am failing to see how AlgoB has a time complexity of O(n). I was expecting it to be O(nlogn) also. Any help would be appreciated.

Assume `n` is a million. How many times will the `for` loop iterate in `B`? — PaulMcKenzie, Feb 01 '22 at 20:53
You may try to prove that the number of stars printed in the second case is between `n` and `2*n-1`, for any `n>0`. — , Feb 01 '22 at 21:05
Note that while the outer loop does the same number of iterations in both, the inner loop doesn't. — molbdnilo, Feb 01 '22 at 21:06
Vague title. Edit to be more specific. Time complexity of *what*? — Basil Bourque, Feb 02 '22 at 00:52

score 1 · Answer 1 · answered Feb 01 '22 at 23:21

Let's look at Algorithm B from a mathematical standpoint.

The number of * printed in the first loop is n. The number of * printed in each subsequent loop is at most n/2. That recurrence relation leads to the sequence:

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

If this were an infinite sequence, then the sum could be represented by the formula n/(1 - r), where r is the factor between terms. In this case, r is 1/2, so the infinite sequence has a sum of 2(n).

Your algorithm certainly won't go on forever, and it each time it loops, it may be printing less than half the stars of the previous loop. The number of stars printed is therefore less than or equal to 2(n).

Because constant factors drop out of time complexity, the algorithm is O(n).

This concept is called amortized complexity, which averages the cost of operations in a loop, even if some of the operations might be relatively expensive. Please see this question and the Wikipedia page for a more thorough explanation of amortized complexity.

Thank you for answering this. This makes sense. Can you explain how you came up with next digits in the pattern like n/4 and n/8 and so on ? — James Franco, Feb 01 '22 at 23:53

score 0 · Answer 2 · answered Feb 01 '22 at 22:13

Algorithm B is printing half the starts at every iteration. Assume n=10, then:

n=10 -> 10*
n=5 -> 5*
n=2 -> 2*
n=1 -> 1*

In total 18* are printed. You will print n + n/2 + n/4 + ... + n/(2^i) stars. How much does i value? It is equal to the number of steps required for n to become 0. In other terms, it is the exponent to which 2 must be raised to produce n: log_2(n). You get the sum in picture:

Which can be approximated to O(n).

Trying to understand the reason for this time complexity

2 Answers2