Time complexity sample question and solution

Question:

Find out the time complexity of the following code. Write proper steps for each instruction.

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

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

                                cout << ‘*’

ANSWER

i = 1	1
i < = n	log3 n + 2
i = i * 3	log3 n + 1
j = 1	log3 n + 2
j < = i	log3 n + 1 + (log3 n + 1)( log3 n + 2) / 2
j = j * 3	(log3 n + 1 )( log3 n + 2) / 2
cout << ‘*’	(log3 n + 1 )( log3 n + 2) / 2

After adding all the above calculated terms we get

T (n) =  O (log n )²)