2^(ceil(log(n)))-1 is the formula for total number of nodes. but if u put n=7 u will get 7 not 15, i m not getting it.
Formula for total number of nodes in segment tree
watch at 57:30 unit in the video.
Total number of nodes= n + (n-1) = 2n-1 Now, we know its a full binary tree and thus the height is: ceil(Log2(n)) +1
Total no. of nodes = 2^0 + 2^1 + 2^2 + … + 2^ceil(Log2(n)) // which is a geometric progression where 2^i denotes, the number of nodes at level i.
Formula of summation G.P. = a * (r^size - 1)/(r-1) where a=2^0
Total no. of nodes = 1*(2^(ceil(Log2(n))+1) -1)/(2-1)
= 2* [2^ceil(Log2(n))] -1 (you need space in the array for each of the internal as well as leaf nodes which are this count in number), thus it is the array of size.
= O(4 * n) approx…