Question

Can I please get help with this question?

Problem 3. How many lines, as a function of n (in 0(.) 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); }

Answer 1

1 { function f(n) 2 { 3 if(n>1) 4 5 print.line("still going"); # this executes constant time 6 f(n/2); # this executes n/2 times f(n/2); # 'this executes n/2 times 8 9} 7 }

Now, the recurrence relation was given by,

T(n)= 1+ T(n/2)+T(n/2) = 2T(n/2)+1

now, by using the masters theorem,

here a=2 and b=2 and k=0

a>b^k  -->2>2⁰ (true) so, T(n)=O(n^{log a}b) =O(n^{log 2}2) =O(n¹) =O(n) case1

Therefore T(n)=O(n)