unacademy

Question

int fun1( int n )

{ int i , j , p =0, q =0;

       for( i =1 ; i < n ; ++i)

      {

             for( j =n ; j > 1; j = j/2)

              ++p;

             for( k =n ; k > p; k = k*2)

              ++q;

      }

       return q;

}

Answer 1

for i=1

p=logn,q=loglogn

i=2

p=2logn,q=loglogn+log2logn

i=3

p=3logn,q=loglogn+log2logn+log3logn

.

.

.

.

.

i=n

p=nlogn

q=loglogn+log2logn+log3logn+......+lognlogn

 

Now using log property of multiplication

log(logn.2logn.3logn........nlogn)

log(logn(1.2.3.4....n))

log(n!logn)

log(n!)+log(logn)

log(n^n)+log(logn) this is Stirling approximation do Google

nlogn+loglogn is final value of q

 

Now talking about time complexity it will O(nlogn)

As outer loop n times

Inner there are two nonnested loops, bigger is upper one so logn

Multiply both so nlogn.

Hope you got it 😊