Question

1. Analyze the running time of the following algorithm and write it using ( notation. You must show detailed calculation/derivation of your running time along with table to get marks. int sum = 0; for (int i=n; i)=1; i=i/2) { for (int j=1; j<=i; j*=2) { sum+=i*j; } }

Answer 1

1.

The 2 for loops in the code segment are not independent and so the product rule cannot be used to compute the time complexity.

Since both i loop and j loop are dependent upon each other, let's analyze how both the loops work using the following table :

Value of i	n	n/2	n/4						1
j loop runs for	log n times	log ( n / 2 ) times	log ( n / 4 ) times						log ( 1 ) times

Let the running time of the algorithm be represented as T(n).

So, the time complexity is calculated as :

T(n) = Sum of the total number of times j loop runs

= log n +  log ( n / 2 ) +  log ( n / 4 ) + .................... log ( 1 )

= log ( n * n /2 * n / 4 .......... 1 ) + 0 [ logarithmic property ]

<= log ( n^n)

<= n log n

So,

T(n) = Θ(n log n)

Hence, the running time of the given algorithm is Θ(n log n).