Time Complexity

Computer Science Level 2

What is the time complexity of the code below?

int count = 0;
        for (int i = N; i > 0; i /= 2) {
            for (int j = 0; j < i; j++) {
                count += 1;
            }
        }

Assume that arithmetic operations take constant time regardless of the size of the input.

\Theta(N^2)

\Theta(N\sqrt{N})

\Theta(N\lg N)

\Theta(N)

\Theta(N\lg (\lg N))

2 solutions

Pranjal Jain
Jul 4, 2015

In the first iteration, the $j$ loop runs $N$ times.

In the second iteration, the $j$ loop runs $N/2$ times.

In the ith iteration, the $j$ loop runs $N/2^i$ times.

So, the total number of runs of loop = $N + N / 2 + N / 4 + … 1\\= N * ( 1 + 1/2 + 1/4 + 1/8 + … ) < 2 * N$

Nice solution! I learned something new. +1. By the way, can you suggest a wiki or material that I can use to read more about determining the complexity of code?

Thanks in advance

Arulx Z - 5 years, 11 months ago

I can't find Time Complexity Wiki on Brilliant. See here

Pranjal Jain - 5 years, 11 months ago

What is the < 2*N part supposed to mean?

David Godfrey - 3 years, 8 months ago

DETAILED EXPLANATION: It means no. of iterations will be less than 2 N.It is because the outer loop runs logN times. N/2^k=1 and on solving we get k=log N where k is the no. of iterations of the outer loop. So,the total no. of iterations will be N (1+1/2+1/4,......) REMARK:No. of terms in the bracket above will be equal to no. of iterations of the outer loop which is logN. Terms inside the bracket forms a gp whose sum=2*(1-(1/2)^logN),which will obviously be less than 2 because term inside the bracket is less than 1.

Therefore total no. of iterations will be <2*N=O(N)

Hardik Padha - 3 years, 5 months ago

IMHO the explanations here are not clear/easy-to-understand, and the answer should be O(N^2). The simple equation for the operations in terms of N is a geometric series with r=4, a0=1, and n = ln(N) + 1; ( ln() here means log to the base 2; refer hre : https://www.varsitytutors.com/hotmath/hotmath_help/topics/sum-of-the-first-n-terms-of-a-geometric-sequence ) . For instance when N=4, the total count will be 4 4 + 2 2 + 1 1 = 21. Which is consistent with the above values. This leads to S(N) = k 2^(2*ln(N)) form.

a b - 2 years, 9 months ago

With the geometric series we actually get O(n):

S= N + N/2 +...+1 .5 S= N/2 +...+1+1/2 ->.5 S= N - 1/2 -> S = 2*N-1 = O(N).

If you are going to test numbers, you should be testing N> 1000000 to get a good idea of the asymptotic behavior.

jason carlson - 2 years, 5 months ago

in the first for loop we have n/2 which means that is log n and in second one we have n , it s a nested loop so it should be nlogn why we got n?

Kalim Nakad - 2 years, 1 month ago

Hey man. I thought this at first but if u think of time complexity as the total sum of operations, then it is simply n+ n/2 + n/4 + n / 8 + ... = (2n-1)

Darren Lim - 1 year, 8 months ago

My first impression was O(n log n) but the answer is O(n).The outer loop does less than O(n) iterations (it actually does O(logn)) so it doesn't affect the big-O complexity.

Boss Joe - 1 year, 4 months ago

Chris Dotimas
Jan 29, 2020

The time complexity of the function can be written as T(n) = O(n + n/2 + n/4 + … 1) = O(n)

at first glance we assume that the first loop is T(logn). after that we can see that the instructions if the nested for gives us a sequence of n+n/2+n/4.... So we can easily assume that the time complexity is equal to the limit of the geometric series.

Demetriou George - 7 months, 3 weeks ago

Time Complexity

2 solutions

0 pending reports