Question

Question 2: Calculate the time complexity function T(n) and express it in terms of big-Oh for the following code:

Part a       (hint: make use of sum of geometric progression):

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

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

            {          

            cout<<”*”;

           

}

}

Part b      (hint: make use of sum of square of a number sequence):

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

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

            {           for (k=1;k<=j;++k)

            {          

                        cout<<”*”;

            }

}

}

Answer 1

Anaswers:

1. O(log²n) or O((log n)²) Both are same
2. O(n³)