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.
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).
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).
algo is Theta(n).