Jump to content

Recurrence relations/ master b

Featured Replies

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!

Archived

This topic is now archived and is closed to further replies.

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.

Configure browser push notifications

Chrome (Android)
  1. Tap the lock icon next to the address bar.
  2. Tap Permissions → Notifications.
  3. Adjust your preference.
Chrome (Desktop)
  1. Click the padlock icon in the address bar.
  2. Select Site settings.
  3. Find Notifications and adjust your preference.