1 votes 1 votes sumit goyal 1 asked Jan 9, 2018 sumit goyal 1 603 views answer comment Share Follow See all 15 Comments See all 15 15 Comments reply Manu Thakur commented Jan 9, 2018 reply Follow Share Height of a node = the length of the path from that node to the farthest leaf node. Depth of a node = the length of the path from the root node to that node. 1 votes 1 votes sumit goyal 1 commented Jan 9, 2018 reply Follow Share what is depth of this tree and also height how to calculate @Manu Thakur 0 votes 0 votes sumit goyal 1 commented Jan 9, 2018 reply Follow Share @Manu Thakur and how to calculate levels 0 votes 0 votes Manu Thakur commented Jan 9, 2018 reply Follow Share level is one more than the height, root node has height 0 and level 1. The total problem is n^2 and you are dividing it into 2 parts each time, so height of the tree should be logn^2 = 2logn 1 votes 1 votes sumit goyal 1 commented Jan 9, 2018 reply Follow Share @Manu Thakur thanks sir i got difference but how you calculating doubt please explain in detail 0 votes 0 votes sumit goyal 1 commented Jan 9, 2018 reply Follow Share @Manu Thakur height given in image = logn not 2log n 0 votes 0 votes Manu Thakur commented Jan 9, 2018 reply Follow Share logn is taken approximately to conclude the time complexity. suppose n=4, n^2 = 16 16 -> 8 > 4 -> 2 -> 1 you can see here height of the tree is 4 that is log4^2 = 2*2 = 4 0 votes 0 votes sumit goyal 1 commented Jan 9, 2018 i edited by sumit goyal 1 Jan 9, 2018 reply Follow Share $(\frac{n}{2^0})^2 + (\frac{n}{2^1})^2 + (\frac{n}{2^2})^2 +....+(\frac{n}{2^k})^2$ clearly levels are 0,1,2.......k = k+1 levels $(\frac{n}{2^k}) =1$ take log we get k = $\log _{2}^{n}$ height = $\log _{2}^{n}$ @ Manu Thakur Ashwin Kulkarni is this correct // 1 votes 1 votes Ashwin Kulkarni commented Jan 9, 2018 reply Follow Share @manu sir, Here each level, while computing for 16, you are doing $\frac{n^2}{2}$ but this is not the case. At each level it is $(\frac{n}{2})^2$ Hence height => $n^2 = 16$ then $(n/2)^2 = 4$ then $(n/4)^2= 1$ Hence ht is $logn$. 1 votes 1 votes Ashwin Kulkarni commented Jan 9, 2018 reply Follow Share Yes it is correct @sumit goyal. And in these type of questions many times you can take approximations too. 1 votes 1 votes sumit goyal 1 commented Jan 9, 2018 reply Follow Share thnku bro 0 votes 0 votes sumit goyal 1 commented Jan 9, 2018 reply Follow Share please check this too @Ashwin Kulkarni suppose they given a reccurrence equation with condition T(2) = 1 in that case $(\frac{n}{2^K}) = 2$ $2^k = \frac{n}{2}$ height = k = $log_{2}^{0.5n}$ right ? iam because i have seen in questions they always mention T(1) =1 0 votes 0 votes Manu Thakur commented Jan 9, 2018 reply Follow Share yes @Ashwin i overlooked the problem. as i am in office, so didn't go in the depth of the recurrence relation problem :) 2 votes 2 votes Ashwin Kulkarni commented Jan 9, 2018 reply Follow Share No problem at all sir :) And yes sumit this is also correct. Why they always gives T(1) = 1, it is according to stoppage of recursion, number of movements. So yes always take a look of halting condition of recursion and then solve it. 1 votes 1 votes sumit goyal 1 commented Jan 9, 2018 reply Follow Share thanks bro 0 votes 0 votes Please log in or register to add a comment.