"Most importantly, I am not convinced about the correctness of the algorithm."
yes i thought it nefore. there is one problem with my method. my
method only ensures that the height of the new tree will be <=
ceiling(log(N+1)). but it is not perfectly balanced. it is possible to
have tree with only right subtree. for example let old tree was
4-3-2-1
then my algo will result in
1
\
3
/ \
2 4
"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.
"
i did not get your point. can you please clarify it with a suitable example??
On 3/18/06, Malay Bag <[EMAIL PROTECTED]> wrote:
> 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 [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
