Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
?
Solved

recurrence relation for binary tree height algorithm?

Posted on 1998-11-10
9
Medium Priority
?
2,961 Views
Last Modified: 2008-02-26
what would the recurrence relation be for the following pseudo code algorithm?

void Height(T)
{
     if (T is not empty)
     {
          lefttreeht = Height(left subtree of T);
          righttreeht = Height(right subtree of T);
         
          if (lefttreeht > righttreeht)
               return lefttreeht + 1;
          else
               return righttreeht + 1;
     }
     else
          return 0;
}

0
Comment
Question by:melissak
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 3
  • 2
  • 2
  • +2
9 Comments
 
LVL 3

Expert Comment

by:arnond
ID: 1254160
do you mean big O complexity ?
if so, it's O(log n), n being the number of nodes in the tree.

Arnon David.
0
 

Author Comment

by:melissak
ID: 1254161
No, I mean;

     base case C(0)=0

recurrence relation for a tree of n nodes:

     C(n) = C(n-1) + something or nothing
     C(n+1) = C(n) + something or nothing

*parenthesis indicate subscript

this is what I think the format should somewhat be but
it could be something different.  I do know that the
explicit formula should be:

     C(n)=log(2)[n+1]-1

which was developed from some recurrence relation.
thanks
mk
0
 
LVL 84

Expert Comment

by:ozo
ID: 1254162
Are you assuming the tree is balanced?
0
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 

Author Comment

by:melissak
ID: 1254163
I don't think it matters.  The definition for the height of a
tree is: the number of nodes on the longest path from the root
to a leaf.  So, worst case binary tree would be one that has nodes attatched to the left or right side only (a diagonal).
0
 
LVL 84

Expert Comment

by:ozo
ID: 1254164
so is C(n) supposed to be the worst case height of a balanced tree of n nodes?
0
 
LVL 16

Accepted Solution

by:
heyhey_ earned 200 total points
ID: 1254165
maybe i am missing something, but if
the explicit formula should be:
     C(n)=log(2)[n+1]-1
than the recurrence relation should be
     C(n+1)=C(n) + log(2)[n+1]
     
0
 

Expert Comment

by:guga
ID: 1254166
I have one comment
if C(n)=log(2)[n+1]-1 then let's n=4

C(n)=log(2)[5]-1;

but height of tree must be integer!
0
 

Expert Comment

by:guga
ID: 1254167
may be (i don't sure)
c(n+1) = C(n) + 1
0
 

Author Comment

by:melissak
ID: 1254168
I had math student help me.  With each call to the algorithm the list of N elements is halved.  Since the algorithm recursively calls itself twice the formula is:
C(N) = 2*C(N/2)
To Prove relation:
Let N = 2^n

C(2^n) = 2*C(2^n-1)
C(2^n-1) = 2*C(2^n-2)
C(2^n) = 2^k * C(2^n-k)
Let k=n
C(2^n) = 2^n * C(2^0) = 2^n

since 2^n = N

C(N) = N

BigOH = O(N)

sorry took so long to respond.  e-mail and internet down.
0

Featured Post

VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
Examines three attack vectors, specifically, the different types of malware used in malicious attacks, web application attacks, and finally, network based attacks.  Concludes by examining the means of securing and protecting critical systems and inf…
The goal of this video is to provide viewers with basic examples to understand and use structures in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use conditional statements in the C programming language.

688 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question