CODEWITHSUNDEEP
algorithmtimewhile-loopcomplexity-theory
Jacek Trociński
Jacek Trociński

Reputation: 920

Determine complexity of algorithm

Assume algo(p) is an algorithm that take Theta(p) time to execute and does not change p. Determine the running time complexity of the following algorithm:

Algo2(n) 
begin
p=1;
while p <= n 
    begin 
    algo(p)
    p=2*p
    end;
end;

Really have no idea where to begin, I was thinking O(logn) maybe since p=p*2 but then there is an algo(p) in the while loop and I don't know how that would effect things.

Upvotes: 1

Views: 297

Answers (2)

Cl&#233;ment Berthou
Cl&#233;ment Berthou

Reputation: 1948

To get an easier problem, you can set it like this :

Algo(n)
  begin
  p=1, i=1
  while p<= n
    begin
    algo(p)
    p=2*p
    i++
    end
  end

which you can rewrite like that : 

Algo(n)
  begin
  i=1
  while 2^(i-1)<=n
    begin
    algo(2^(i-1))
    i++
    end
  end

Then, as Henrik said :

It calls algo(p) O(logn) times with p = 1, 2, 4, ..., 2^(floor(logn)). This is Theta(1 + 2 + ... + 2^(floor(logn)) = Theta(2^(floor(logn+1)-1) = Theta(n).

Upvotes: 0

Henrik
Henrik

Reputation: 23324

It's Big Theta(n):

It calls algo(p) O(logn) times with p = 1, 2, 4, ..., 2^(floor(logn)). This is Theta(1 + 2 + ... + 2^(floor(logn)) = Theta(2^(floor(logn+1)-1) = Theta(n).

Upvotes: 3

Related Questions