Time complexity analysis of different looping program

 Analyze the time complexity of below function

Q1)

A()

{

    i=1;

    s=1;

    while(s<=n) 

    {

        i++;

        s=s+i;

        print "hi"

    }

}

for n=15 the values of i and s inside while loop as shown below:

i 1 2 3 4 5

s 1 3 6 10 15

for n=15, the while loop runs 5 times ..i.e, approximately sqrt(n) times

so time complexity = O(sqrt(n))

In depth explanation:

Let this while loop runs k times and after k iterations,

s would be sum of first k natural numbers.

and s must be >= n to come out of the loop

(k*(k+1))/2 = n

k*k+k >2*n

k*k approximately equal to n

k is approximately equal to sqrt(n)

===========================================

 Analyze the time complexity of below function

Q2)

A()

{

    i=1;

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

    {

        print "hi"

    }

time complexity = O(sqrt(n))

===========================================

Analyze the time complexity of below function

Q3) 

A()

{

    int i,j,k,n;

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

    {

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

        {

            for(k=1;k<=100;k++)

                print "hi"

        }

    }

}

                    |i=1       |i=2 |i=3

j loop runs         |1 time      |1,2 that is 2 times |1,2,3 that is 3 times     

for each j k runs |100 times |2*100 times |k=3*100

= 100+2*100+3*100 +.....+n*100

                    = 100*(1+2+3+............+n)

                    = O(n*n)

==============================================================

Q4) 

A()

{

    int i,j,k,n;

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

    {

        for(j=1;j<=i*i;j++)

        {

            for(k=1;k<=n/2;k++)

                print "hi"

        }

    }

}

                    |i=1       |i=2 |i=3 ..........n

j loop runs         |1 time      |1,2,3,4 i.e, 4 times |3*3=9 times......n*n     

for each j k runs |n/2 times |4*n/2 times |9*n/2........(n*n)* n/2

= n/2+4*(n/2)+9*(n/2) +.....+(n*n)* (n/2)

                    = n/2*(1+4+9+............+n*n)

                    = n/2*(n*(n+1)*(2*n+1))/6

                    = O(n*n*n*n)

====================================================================

Q5) 

for(i=1;i<n;i=i*2) 

{

print "hi"

}

i will take values 1,2,4....n

2^0, 2^1, 2^2.....2^k

2^k =n and k=log2(n)

===================================================================

Q6)

while(n>1)

{

n = n/2

}

if n=16 then 16,8,4,2..4 times ...log2(16) = log2(n) times

======================================================================

Q7)

for(i=n/2;i<=n;i++) ........................n/2 times

    {

        for(j=1;j<=n/2;j++) .............. n/2 times

        {

            for(k=1;k<=n;k = k*2) ....... log2(n) times

                print "hi"

        }

    }

= (n/2)*(n/2)*log2(n) = n*nlog2(n)

===========================================================================

Q8)

for(i=n/2;i<=n;i++) ........................n/2 times

    {

        for(j=1;j<=n;j = 2*j) .............. log2(n) times

        {

            for(k=1;k<=n;k = k*2) ....... log2(n) times

                print "hi"

        }

    }

= (n/2)*log2(n)*log2(n) = n*log2(n)*log2(n)