Give the running time for each example Justify your answers

Give the -running time for each example. Justify your answers

for i = n; i > 0; i = i 4 do

for j = i; j < n; j + + do

· · ·

end for

end for

Solution

Since first loop decreases by 4 the time is log n

=T(n)*T(log n)

here there are two for loops hence the total time complexity is given by theta(n log n)