Solving the recurrence relation $T(n)=T(n−\lceil\sqrt{n}\:\rceil)+\Theta(n)$

Asked Oct 30 '16 at 13:38

Active Oct 30 '16 at 17:51

Viewed 32 times

I have an algorithm that at each step can discard $\lceil\sqrt{n}\:\rceil$ possibilities at a cost from $O(n)$. The solution to the recurrence relation below is related to the question of complexity of such algorithm:

$$T(n)=T(n−\lceil\sqrt{n}\:\rceil)+\Theta(n)$$

how should i solve?

edited Oct 30 '16 at 17:51

Rick Decker

8,718

asked Oct 30 '16 at 13:38

M.Dara

A very rough heuristics. If $T(n)\equiv C\cdot n^a$ then $C\cdot n^a\equiv (n-n^{1/2})^a+n\equiv n^a-an^{a-1}n^{1/2}+\Theta(n)$. If $n^{a-1}n^{1/2}=\Theta(n)$ then $a=3/2$. – Alex Ravsky Oct 30 '16 at 14:34

Solving the recurrence relation $T(n)=T(n−\lceil\sqrt{n}\:\rceil)+\Theta(n)$

0 Answers0