Question

4. Given Pseudocode:

Algorithm3(n):

y = 0

for i = 1 to n do

y = 1

while y < i² do

y=2y

return y

a. What's the output of Algorithm3(n) as a function of n?

b. What's the running time of Algorithm3(n) as a function of n? Represent this as a summation.

c. Prove the running time to be O(n log n).

Answer 1

A) Look at the below Python code and its output.

def algorithm3(n):

  y = 0 # This will take constant time (assignment operation)

  for i in range(1,n+1): # This loop will run n times 
    y =1 # This will take constant time (assignment operation)

    while (y<(i*i)): # This loop will run logn times
      y = 2*y # This will take constant time (assignment operation)

  return y 

for i in range(1,21):
  print(algorithm3(i))

B) The first for loop will run n number of times and the subsequent while loop will run logn number of times.

So overall time complexity will be O(n)*O(logn) = O(nlogn).

C) When the iterator value of any loop gets divided or multiplied by a constant factor than its time complexity will always be logn. Beacuse in that case the iteration happens for that constant factor instead of normal unit value iteration.

Happy Learning!