calculate depth of tree given in image , do height and depth are different things ??

Question

Comments

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.

---

what is depth of this tree and also height how to calculate  @Manu Thakur 

---

@Manu Thakur  and  how to calculate levels 

---

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

---

@Manu Thakur thanks sir i got difference but how  you calculating doubt please explain in detail

---

@Manu Thakur height given in image = logn  not 2log n

---

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

---

$(\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      //

---

@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$.

---

Yes it is correct @sumit goyal.

And in these type of questions many times you can take approximations too.

---

thnku bro

---

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  

---

yes @Ashwin i overlooked the problem. as i am in office, so didn't go in the depth of the recurrence relation problem :)

---

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.

---

thanks bro