What would you call the time complexity of an algorithm of this sort?

Question

I am using C# syntax but this question is not specific to C# only.

Example 1

public static long Do(long n)
{
    var sqrt = (long)Math.Sqrt(n);

    for(long i = 0; i < sqrt; i++)
        // do something

    return result;
}

Would that still be linear time even though even in the worst case, we're doing the operation for only the square root times of n, which is a very small fraction of n?

Example 2

And how would you classify the time-complexity of the algorithm below?

public static long Do(long n)
{
    while (n > 1)
    {
        n = (long)Math.Sqrt(n);

        // do something
    }

    return result;
}

Would this be called an operation done in logarithmic time in the worst case, even though we're, once again, not just halving the number of iterations each time but reducing them by an order of magnitude more than just the half.

Answer 1

The first code snippet contains only one loop and a constant number of operations outside of this loop. If this loop iterates k times while each iteration takes t time, it's complexity is O(kt). Here, k is equal to sqrt(n) which means that if the loop contains no non-constant time operations (say, if it does not contain nested loops or recurrent functions, etc), then this snippet time complexity is equal to O(sqrt(n)) which is also written as O(√n).

The fact that there's a loop here does not mean anything in terms of complexity. For example, the following code, having two nested loops, has a linear complexity:

int j = 0;
for (int i = 0; i < n; ++i)
{
    for (; j < n; ++j)
    {
        // A loop with constant-time operations and eventual breaks
    }
}

In this example, i goes from 0 to n, thus we spend O(n) time on increasing i. Similarly, j goes from 0 to n, and we do O(n) increments of j variable as well as O(n) iterations of the inner loop body. Since we have no other operations in this code, the total complexity is O(n) + O(n) + O(n) = O(n).

To deal with the second example, I rewrite it in recursive manner:

int Do(int n)
{
    // Do something with constant-time compexity
    return n > 1 ? Do(sqrt(n)) : result;
}

Let us call time complexity of this example as T(n). We can see that T(n) = 1 + T(sqrt(n)) where the time of calculation of first part of this function (which is constant) is taken as a time unit. Solving this recursive equation gives us T(n) = log log n (the logarithm here is binary). Indeed, 1 + log log(sqrt(n)) = 1 + log ((log n) / 2) = 1 + log log n - 1 = log log n. For asymptotic expressions it does not really matter which base of logarithm you use, since log_a x = log_a b * log_b x = O(log_b x), that's why typically the logarithm base is omitted.

So, the complexities are: O(√n) and O(log log n).

UP: To non-strictly estimate your complexities, one may use Excel or any other software tool for calculation. You need just build a table of numbers of operations for different values of n and try to guess a complexity rule. For example, for code snippet #2 from the question:

N  Operations  log n  log log n 
1       1        0        -  
2       2        1        0
4       3        2        1
16      4        4        2
256     5        8        3
65536   6        16       4

The correct answer is typically obvious from the table