What is the time complexity Big-O of this algorithm?

What is the time complexity Big-O of this algorithm?

, The first assumption it's O(N * lg N) but it is not correct, why?

        count = 0
for i = N : 1 {
for j = 0 : i {
count = count + 1
j =  j + 1
}
i = i/2
}
print(count)

• Big-O of what? Time complexity or count or space complexity? – Mr. Sigma. May 13 at 6:54
• What language is this? – Stig Hemmer May 13 at 8:23
• @Mr.Sigma. I am asking about the Time complexity – sc0der May 13 at 12:53
• @greybeard i decrement the half each iteration. will start from N, N/2, N/4, N/8,....,N/N – sc0der May 13 at 12:55
• It’s clearly n^2 because I iterates from n down to 1, and changing I doesn’t affect this. – gnasher729 May 14 at 7:06

The second for-loop while be executed N + N/2 + N/4 +....+ N/N

, the first for-loop decides how much the second for-loop will be executed.

When i = 0, j loops until N

, i = N/2, j loops until N/2

, And so on

, The Big O notation of N + N/2 + N/4 +....+ N/N will be O(N)

The runtime for this algorithm is $$\Theta(n)$$.

By rewriting the iterative formula as a recurrence relation $$T(n)=T\left(\frac{n}{2}\right) + n$$ we can use Master Theorem to analyze the runtime. The recursive equation doesn't meet the criteria for the first or second cases but it does meet those for the third, meaning $$T(n)=\Theta(f(n))$$ where $$f(n)$$ is the amount of work done at each iterative level of the algorithm; in this case $$f(n)=\Theta(n)$$ and so $$T(n)=\Theta(n)$$.

• Well, $\Theta(n) \subset O(n \lg n)$. – greybeard May 13 at 8:31
• @greybeard Yes, that's true, but it also holds that $\Theta(n)\subset O(2^n)$ but that doesn't make $O(2^n)$ a useful upper bound for the algorithm's runtime. You're absolutely correct in your assertion but it's a bit like being asked what the upper bound for the height of a human being is and answering "50 meters". Sure, it's true, but it doesn't actually tell me much about how tall people are. – Or Bairey-Sehayek May 13 at 10:44

*Cough* Nice homew... Ahem

It's O(N*log(N)) because the outer loop runs log(N) times (i from N to 1, dividing by 2 each time) and the inner loop runs i times (so N times the first time for example, then less).

• The outer loop run from N, N/2, N/4,..N/N – sc0der May 12 at 21:27
• Yes, and N, N/2, N/4... to 1 is log(N) (in base 2) steps. – d3m4nz3 May 12 at 21:28
• Imagine N is 2^32 (approximately FOUR BILLION) and log(N) = 32. Outer loop will run 32 times. Inner loop will run 2^32 times, 2^31 times, 2^30 times... So inner loop is N. – d3m4nz3 May 12 at 21:33
• the inner loop will n, n/2, n/4, n/8, .... – sc0der May 12 at 23:06
• the inner doesn't iterate n each time – sc0der May 12 at 23:08

there is two loops .. the inner loop over O(N) numbers(0 to i at most i=N) and the outer one starts the loop from N and slice it by two in each iteration (N -> N/2 -> N/4 ..) therefore the big-O of the algorithm is O(Log(N)*N).

• the inner loop will n, n/2, n/4, n/8, .... – sc0der May 12 at 23:07
• you are right .. this big-O not the asymptotic..i edited my answer – Obida Asad May 13 at 0:19
• How does your argument for (runtime in) $O(\log N \times N)$ answer assumption [O(N * lg N)] is not correct, why? – greybeard May 13 at 8:27

A more practical approach:

The most executed statements in this example is the ones inside the innermost loop, for example

count = count + 1


This statement counts how many times it is executed, which means that the total runtime is approximately proportional to the output.

So, try to run this program with various inputs and see what the output is. I don't know this language, so I don't know the exact semantics, but it seems that the approximate count is $$2N$$.

Knowing this answer should put you on the right track to finding out why.

When the value of i is N, the inner loop will run N times

Then, the value of i becomes N/2, so the inner loop will run N/2 times

then, the value of i becomes (N/2)/2, so the inner loop will run N/4 times

This continues till the value of i becomes 1, so the total time complexity is : $$N + N/2 + N/4 + N/8 + ....... + 1$$

Or $$1 + 2 + 4 + 8 + 16 + ..... N/2 + N$$

Total number of terms in this is t= $$log2(N)$$ ignore lower terms(constants) in the calculations below(for the sake of Big O Notation):

summing up we get $$2^t-1 = log(N)$$ Thus, time complexity is O(N)

Forget about the outer loop. Just remember that on it's way from $$N$$ to 1, $$i$$ gets divided by $$2$$ on each iteration.

Now, on the first iteration of the second loop, $$j$$ will go from $$0$$ to $$N$$, and so we will have $$N-0+1 = N+1$$ steps. On the second iteration, $$j$$ will go from $$0$$ to $$\frac N2$$, so we will have $$\frac N2 + 1$$ iterations. You can see how this evolves: $$(N + 1) + (\frac N2 + 1) + (\frac N4 + 1) + \dots + 2.$$

For simplicity, let's remove the $$1$$'s from each term because their effect on $$N$$ is insignificant as $$N \rightarrow \infty$$.

Now, all you have to do is sum up $$S = N + \frac N2 + \frac N4 + \dots + 1$$.

Factorizing $$N$$ gives $$S = N(1 + \frac 12 + \frac 14 + \dots +\frac {1}{2^n}) = N \sum_{k=0}^{n} (\frac 12)^k$$.

The result of the sum (using the formula of a finite geometric series) is $$2(1-(\frac 12)^{N+1})$$. As $$N\rightarrow \infty$$, this sum tends to $$2(1-0) = 2$$.

Finally, we have that $$T(N) = \Theta(2N) = \Theta(N)$$.

• i gets divided by 2 on each iteration What will be the value of $i$ at the start of the next iteration (if any), and how do you know? – greybeard May 13 at 23:02
• @greybeard From the given code: i = N : 1. It's obvious, i is $N$ on the first iteration. Before the start of the second, we have i = i/2, hence the value of i on the second is $\frac N2$. Are you sure you understand the code? – user821 May 14 at 5:14
• (Values from start value N halved in each iteration could have been gleaned&assumed even by me from the the inner for-loop showing explicit increment of the control value. I assumed implicit decrement in the outer one - not that that would have changed the tight asymptotic boundary unless it was the type "the control variable takes on every value from start to end in turn unless stated otherwise in the for construct".) (Know for-right-part?) – greybeard May 14 at 5:27