In the longest branch we have atmost logN calls. Array size at first call =n/2, next call call=n/4 … . So, total size of all the arrays in the call stack = n + n/2 + n/4 … . Why did Prateek bhaiya sum up the number of steps and not the size of each array in the call stack as I did ?
Doubt at 5:18 regarding space complexity
@girishgargcool function calling is being done logn times n,n/2,n/4 … thats why steps , not actually n,n/2 …
But the total SIZE of the array being stored in the array is n + n/2 + n/4 … . Why are we not summing the size when calculating the space complexity?
@girishgargcool if you are talking about array size then n+n/2+n/4… is approx 2*n which is also o(n) only