GATE Overflow Test Series | Algorithms | Test 1 | Question: 18

Question

What is the time complexity of following code if $foo(n)$ takes $\Theta(\log n)$ time to execute?

int i, j; 
for (i = n / 2; i <= n; i++) { 
    for (j = 1; j <= n; j = j * 2) { 
        foo(j); 
    } 
}

• A. $\Theta(n)$
• B. $\Theta(n \lg n)^2$
• C. $\Theta(n (\lg n)^2)$
• D. $\Theta(n^2 \lg n)$

Answer 1

The $i$ loop iterates $n/2 = \Omega(n)$ times.
 
 $j$ loop does call to foo(j). So, enumerating the calls to foo(j) we get
 
$ foo(1) + foo(2) + foo(2^2) + \ldots + foo (2^{\lg n})$
 
 Complexity of $foo(k) = \Theta(\log k)$
 
 So, we get complexity of $j$ loop as
 
 $ \Theta(\lg 1) + \Theta(\lg 2) + \Theta(\lg 2^2) + \ldots + \Theta(\lg 2^{\lg n})$
 
 $ = \Theta (1 + 2 + 3 + \ldots + \lg n)$
 
 $ = \Theta ((\lg n)^2)$
 
 So, the time complexity of entire code $ = \Theta(n (\lg n)^2).$