I'm reading one cool book, and there was a task to determine the time complexity of the code in the worst case. The code performs integer division (a > 0, b > 0):

int div(int a, int b) {
    int count = 0;
    int sum = b;
    while (sum <= a) {
        sum  = b;
        count  ;
    }
        
    return count;
}

My answer was O(n), since, in the worst case, when we have a > 0, b = 1, we will iterate through a times in the while() loop.

The answer in the book was O(a/b) which makes sense. But, if we're considering the worst case, then

O(a/1) => O(a) <=> O(n) (letter in parentheses doesn't really matter in this case).

So, the answer O(n) is correct as well. Isn't it?

CodePudding user response：

Your answer does not make sense for the simple reason that there is no n in the problem statement, and saying that a is n is "cheating".

Also, though it is technically correct, it is a little sad to use an untight bound O(a) when you know that the algorithm makes exactly a/b additions.

By the way, it is an arbitrary decision to say that b=1 is "the" worst case. Better say worst case for fixed a (and variable b), or for fixed b (and variable a).

CodePudding user response：

Alas there is no generalisation of big-O to multi-variable one, see Formal definition of big-O when multiple variables are involved?.

But as you know the exact complexity, T(a,b)=a/b, there is no need for worst-case... We use worst-case analysis when we don't know how to compute the exact complexity.

CodePudding user response：

The answer is still O(a/b) there is no O(n).