Time complexity of algorithm (Big O, Omega)

Question

I'm trying to understand time complexities better and I was hoping someone could help me figure out the time complexity in the worst case for the following algorithm (in pseudocode):

for i= 0 to n−1:
    if A[i] < 0:
        b= 1
        while b < n:
           b=b×2
    end while
  end if
end for

upper-bound and lower bound of what ? Of the algorithm or of the worst case ? — , Sep 24 '21 at 12:46

score 1 · Accepted Answer · answered Sep 24 '21 at 12:47

1

Hint:

The inner loop is executed Θ(log n) times - when it is executed - because it exits when b has as many bits as n.

Now the worst case happens when all A[i] are negative, so that the inner loop is executed n times.

answered Sep 24 '21 at 12:47

Thank you! I was mostly confused by the inner loop so this has cleared it up for me – bennietgek Sep 24 '21 at 13:07

Time complexity of algorithm (Big O, Omega)

1 Answers1