@Gene : i guess you are considering balanced tree.
what if the tree is left skewed or right skewed .
then height of thee will ne H=No. of node.
so we will get :-
1+2+3+4....H
so recurrence will be T(n) = T(n-1) + O(n)
hence complexity will be O(N^2)
correct me if i am missing somthing.
Thanks in advance.
On Sun, Nov 20, 2011 at 3:40 PM, Gene <gene.ress...@gmail.com> wrote:
> My advice is don't guess. Do the math.
>
> To print level L of a perfectly balanced tree, you will traverse 2^L
> -1 nodes.
>
> The outer loop that prints levels 1 .. H will therefore traverse
>
> sum_{L=1..H} (2^L - 1) = 1 + 3 + 7 + ... 2^H - 1
>
> Let N = 2^H - 1 be the number of nodes in the tree. Then
>
> sum_{L=1..;H} (2^L - 1)
> = sum_{L=1..H} (2^L) - H
> = 2^(H+1) - 2 - H
> = 2 N - log(N+1)
> = O(N)
>
>
>
> On Nov 20, 7:13 am, Ankuj Gupta <ankuj2...@gmail.com> wrote:
> > I guess its NlogN for balanced tree as it is traversing N nodes for H
> > times ie the height of tree which is logN for balanced and N for
> > skewed tree. So it should be Nlogn and N^2
> >
> > On Nov 20, 9:27 am, tech coder <techcoderonw...@gmail.com> wrote:
> >
> >
> >
> > > @ sravanreddy001
> > > complexity is O(N^2) whether tree is balanced or not doesn't matter
> > > For each level it's visiting elements. all elements upto n-1 level .
> > > i dont know from where u got the concept of logn , the code is not
> > > making any decision to go in left or right , it is going in left and
> right
> > > both , so how it is nlogn.
> >
> > > On Sun, Nov 20, 2011 at 3:12 AM, sravanreddy001 <
> sravanreddy...@gmail.com>wrote:
> >
> > > > Its NlogN if balanced.. Else N^2
> >
> > > > For each element it's visiting at most log N elements.(assuming
> balanced)
> >
> > > > --
> > > > You received this message because you are subscribed to the Google
> Groups
> > > > "Algorithm Geeks" group.
> > > > To view this discussion on the web visit
> > > >https://groups.google.com/d/msg/algogeeks/-/hVQH5EtOfK4J.
> > > > To post to this group, send email to algogeeks@googlegroups.com.
> > > > To unsubscribe from this group, send email to
> > > > algogeeks+unsubscr...@googlegroups.com.
> > > > For more options, visit this group at
> > > >http://groups.google.com/group/algogeeks?hl=en.
> >
> > > --
> > > *
> >
> > > Regards*
> > > *"The Coder"*
> >
> > > *"Life is a Game. The more u play, the more u win, the more u win , the
> > > more successfully u play"*- Hide quoted text -
> >
> > - Show quoted text -
>
> --
> 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
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
