thts not true
first of all n is height of the new tree i.e. ceiling[log(N+1)] where
N is the no. of node in the old tree.
N <= 2^n - 1
and T(n) = T(n-1) + T(n-2) + .. + T(0) + cn
T(n-1) = T(n-2) + ... + T(0) + c(n-1)
so T(n) = 2T(n-2) + 2T(n-3) + .. + 2T(0) + cn + c(n-1)
T(n-2) = T(n-3) + .. + T(0) + c(n-3)
so T(n) = 4T(n-3) + ... + 4T(0) + cn + c(n-1) + c(n-2)
in this way you will get T(n) = 2^(n-1)T(0) + c(n + n-1 + n-2 + .. 1)
now T(0) = O(1)
so T(n) = 2^(n-1)O(1) + O(n^2)
= O(N) + O((logN)^2) = O(N) as N>>logN
so effectively the alfgo runs in O(N) time where N is no of node
On 3/18/06, Padmanabhan Natarajan <[EMAIL PROTECTED]> wrote:
> Hi Malay,
>
> I don't see how you algorithm takes O(n) time or O(logn) space, The use of
> recursion should take into account the implicit stack.
>
> for(int i = 0; i < n; i++)
> process(height - 1)
>
> itself transforms into recurrence T(n) = nT(n - 1) + O(1)
> You will see that this is exponential (forget about linear, its not even
> polynomial). Also the space requirement is n + n - 1 + n - 2....1 = O(nexp2)
>
> Most importantly, I am not convinced about the correctness of the algorithm.
>
> For a chain of considerable length yours will contine you to be unbalanced
> except that most of the nodes will have left and right children, a simple
> test per your algorithm the root of the original chain continues to be the
> root of the final result, which is not true.
>
> Thanks & Regards,
> Padmanabhan
>
>
> On 3/13/06, Malay Bag <[EMAIL PROTECTED]> wrote:
> >
> >
> > node *root;
> >
> > node * build(int height)
> > {
> > node *r, *temp;
> > for(i=1, r=null; i<=height && root; i++)
> > {
> > temp = root;
> > root=root->left;
> > temp->right=r;
> > r=temp;
> > r->left = build(i-1);
> > }
> > return r;
> > }
> >
> > void main()
> > {
> > node *tree;
> >
> > tree = buld(n); // n=height of of new tree
> > }
> >
> > i think this will take O(N) time and logN space... plz check
> >
> >
> >
>
>
>
>
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
