Test by Bikram | Algorithms | Test 2 | Question: 2

Question

Find the time complexity of the function

function( int n)
{
    int i=1;
    while( i<n)
    {
        int j=n;
        while( j>0)
            j=j/2;
            i=2*i;
    }
}

• A. $O(\log n)$
• B. $O(n^2 \log n )$
• C. $O(\log 2 n)$
• D. $O( \log n^2 )$

Comments

Yeah correct... I mistakenly thought it inside may be because of indentation...in that case answer is O(logn) right?

---

Yes.. If both statements will be inside inner while loop then O(logn).

But here O(log²n) is correct..

---

Yes

Answer 1

here int the code
while(j>0)
j=j/2;//log n time

i=2*i // log n time

so O( log n *  log n)=O(log² n)  

as (log n)^k = log^k n.

Like, x = log n, then x² = (log n)² = log n * log n = log²n.

Comments

Ok if u r saying : (log n)^2 =log n*log n = log^2 n

then please tell me

log log n =??

---

$\log \log n$ is simply  $\log(logn)$, nothing else.

---

NO ........

u will check in class 11 or 12 it is given

(log n) ^2= log n * log n

log ^2 n= log log n

Answer 2

consider n=8

i=1 ...given

j=8

inner while loop j= 4 , 2 , 1   and  i= 2, 4 , 8

outer loop will break nxt time

so, O(logn)

Answer 3

this question answer is given wrong. representation of logN*logN is not like that .