2
i = n
while (i >= 1)
{
    for j = 1 to i 
    {
    Function() <- (O(1))
    }
i = i/2
}

The answer is Theta(n) but I do not understand why this is Theta(n).

From my understanding, the inner loop will execute n + n/2 + n/4 +...+1 so the total will be O(n) and the outer loop will be executed logn time so the answer should be nlogn. But why this is Theta(n) instead of Theta(nlogn)?

NoSleep
  • 127
  • 1
  • 10
  • Possible duplicate of [Big O, how do you calculate/approximate it?](http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) – Paul Hankin Jan 17 '17 at 22:50

5 Answers5

4

As you correctly noted, the inner loop will be executed n + n/2 + n/4 + ... + 1 ≈ 2*n times.

Let's see how many times each line of code will be executed.

i = n                  // Executed 1 time
while (i >= 1)         // Executed approximately log(n) times
{
    for j = 1 to i     // Executed approximately 2*n times
    {
        Function()     // Executed approximately 2*n times
    }
    i = i/2            // Executed approximately log(n) times
}

So the total time complexity of the algorithm is:

Θ(1) + Θ(log(n)) + Θ(n) + Θ(n) + Θ(log(n))

Which is equivalent to Θ(n).

Anton
  • 3,113
  • 14
  • 12
3

From my understanding, the inner loop will execute n + n/2 + n/4 +...+1 so the total will be O(n)

That's all you need. You've already taken into account the multiplying effect that the outer loop has on the number of times the inner loop runs. The fact that the outer loop's complexity itself is O(n) can be added to the inner loop's total complexity. The total is not n * log n, it's n + log n, which is O(n).

StriplingWarrior
  • 151,543
  • 27
  • 246
  • 315
  • Thank you for your answer. I am not sure when do I need to add the inner loop's complexity to the outer loop's complexity. For example, if I have for(int i = 0; i < N; i++) for(int j = i; j – NoSleep Jan 18 '17 at 00:20
  • Just count how many times `func()` is called, there is no general rule, each case needs its own figuring out. – Selçuk Cihan Jan 18 '17 at 08:34
  • @NoSleep: The inner loop in that last example will run `func()` `N` times each time it runs, but you were able to separate that concept from the number of outer loop runs because it runs the same number of times regardless of the outer loop's state. In the original question, you didn't estimate the number of times the inner loop ran *independently of the outer loop* because the inner loop depended directly on the value of `i` from the outer loop. So `O(n)` already took into account the effect the outer loop had on the inner loop. – StriplingWarrior Jan 19 '17 at 23:04
1

You're right about the total inner loop executing n + n/2 + n/4 + ... + 1 which is O(n). You don't have to multiply the inner loop's runtime by O(log(n)), since while the outer loop has a runtime of O(log(n)), the inner loop's runtime also decreases by log(n) as you divide i by 2, thus the runtime is simply just O(n)

TheAmateurProgrammer
  • 9,252
  • 8
  • 52
  • 71
  • If I understood correctly, if the outer loop has smaller complexity than inner loop then, I do not need to multiply those two complexity. Is this correct? Thank you. – NoSleep Jan 18 '17 at 00:22
  • I think its better to understand it if you only consider how many times `Function()` (and other operations) is called, in which you have accomplished with the summation. – TheAmateurProgrammer Jan 18 '17 at 14:28
1

Your calculations are partially correct. You are simply missing out on a small detail in which you have already calculated the outer loop's complexity. In your case, you chose to calculate time complexity by simply calculating the time each iteration in the outer loop takes. And that is:

for i=n : O(n)

for i=n/2: O(n/2)

.
.
.

for i=1: O(1)

Now, the calculations for each iteration where made based on the time complexity of the inner loop. Therefore, the total time complexity is how much the outer loop takes (which includes the time the inner loop takes) which is the sum of how much it takes to run each iteration which is: n+n/2+n/4+...+1.

The multiplication you were referring to is a technique used when you know how many times the outer loop runs and how many times the inner loop runs and you multiply them to get the overall time complexity. You could have alternatively, added the number of times the inner loop runs to itself n times whereas n is the number of times the outer loop runs (simple mathematics: k*n = k+k+...+k n times).

So in your case, you're simply using the second method, since n+n/2+n/4+...+1 is not the number of times the inner loop runs, it's the sum of how many times it runs in each iteration of the outer loop.

RoaaGharra
  • 710
  • 5
  • 19
0

The sum of n + n/2 + n/4 ... + 1 is always smaller or equal than 2*n, because the geometric series for q = 0.5 converges to this.

Therefore, the function will never be called more than 2n times so the complexity is Θ(n).

koalo
  • 2,113
  • 20
  • 31