Jump to content
Urch Forums

A Recurrence Relation


dionysus

Recommended Posts

Yes O(n) is the right answer. I worked it out using recursion trees.

T(n) -----> T(n/2) ----> T(n/4)
      |             |
      |             --------> T(n/8)
      |
      -----> T(n/4) -----> T(n/8)
                     |
                     --------> T(n/16).

and so on. With some handwaving, one can assert the following, the number of nodes at depth I is less than or equal to 2^i. And the cost of level I is 1 per node on that level. So the total cost = Sum_{i=0}^{depth} 2^i = 2^{depth + 1} - 1. Now depth = log_2 n, so that total cost = 2n - 1 = O(n).

 

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Restore formatting

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...