Finding the time complexity of doing k += sqrt(k) in a loop

Viewed 162

Given this code:

int f(int n)
{
    int j = 10;
    while( j < n) {
        j += sqrt(j);
        printf("Hello\n");
    }
    return j;
}

How can I find its Time Complexity, the solution is O(sqrt(n)) but still why?

Thank you for your time <3

What I was able to find is that the variable j belongs to a sequence u n+1=un+sqrt(un), trying and trying to find its general term didn't lead me anywhere, I also tried using a generating function for it but still didn't work.

0 Answers
Related