I have this homework question.
How many lines as a function of n (in O( )) form does the following program print? Write a recurrence and solve it. You may assume n is a power of 2.
function f(n)
if n>1:
print_line('Still Going')
f(n/2)
f(n/2)
The recurrence relation I came up with is 2T(n/2)+ O(1) so a=2, b=2 and d=0.
So by my understanding of the master theorem the number of lines printed is O(n)
But that doesn't feel correct to me. Since the size of the problem is being reduced by half each time, it seems the answer would be O(lg(n)). So my questions are,
1. Did I set up my recurence relation correctly.
2. If 1, then did I apply the master theorm appropriately?
3. If (1&&2) why is the answer O(n). Does it have to do with the fact that there are two recursive calls to f(n)?
Thanks!
