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?