Give the running time for i n i 0 i i 4 do for j i j n

Give the -running time

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

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

· · ·

end for

end for

Solution

the first loop of i runs from n to 0 (not inclusive) but at multiples of 4 . Hence loop runs n/4 times.

the next loop runs for n-i times for every value of i.

hence both loop runs n² times ignoring the constants and + and - terns associated with lesser degrees of n

So complexity of this would be (n²)