Find the time complexity function and big-O for the following code segments.

Find the time complexity function and big-O for the following code segments.  Show all working

Part    part a:

for (i = 1; i < N; i = i * 5)

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

cout<<”*”;

        

           SOLUTION

The       frequency of the inner loop is : 1+5+25+125+…+N, which is a geometric progression with sum  given by:

                             (5N-1)/4

                                                                    

            So for individual statements we have:

Statement	Frequency
i=1	1
i<N	log5N+1
i=i*5	log5N
j=0	log5N
j<i	(5N-1)/4+ log5N
j++	(5N-1)/4
cout << ‘*’	(5N-1)/4

               T(N) = 15N/4 + 4 log₅N – 5/4 = O(N)

Part part b:

for (i = 1; i < N; i = i * 5)

for (j = 0; j < N; j = j+4)

cout<<”*”;

SOLUTION

Here the two loops are independent.  For individual statements we have:

Statement	Frequency
i=1	1
i<N	log5N+1
i=i*5	log5N
j=0	log5N
j<N	log5N*N/4 + log5N
j=j+4	log5N*N/4
cout << “*”	log5N*N/4

T(N) = 3/4*N log₅N + 4 log₅N +2 = O(N log N)