I'm trying to analyze the time complexity of the following recurrence relation using the recurrence tree method:
T(n) = T(n - sqrt(n)) + n^2
The challenge I'm facing is determining the height of the recurrence tree because the term being subtracted from n
is sqrt(n)
, which is dependent on n
itself.
help me in calculating height of this form of trees.
I attempted to divide n by its square root, assuming it was a constant, but that approach doesn't make sense to me. I am looking for a mathematical proof of how to calculate the height of the recursion tree and the overall time complexity. Any references would be appreciated.