Determine the time complexity of an algorithm

Question

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?

i think you wrote sub instead of sum inside your while condition — Olli
– Olli, Commented Dec 8, 2022 at 8:55

Jean-Baptiste Yunès · Accepted Answer · 2022-12-08 10:04:08Z

2

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.

answered Dec 8, 2022 at 10:04

Jean-Baptiste Yunès

36.6k4 gold badges51 silver badges76 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

user1196549 Over a year ago

Also when we want to remain on the safe side.

score 2 · Accepted Answer · 2022-12-08 11:42:48Z

2

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).

edited Dec 8, 2022 at 11:42

answered Dec 8, 2022 at 8:57

user1196549

2 Comments

Serhii Chernikov Over a year ago

From the task description, I know that a and b are always > 0.

user1196549 Over a year ago

@SergeyChernikov: you are right. I am rephrasing.

Collectives™ on Stack Overflow

Determine the time complexity of an algorithm

2 Answers 2

1 Comment

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related