'What is the best and worst case for the following snippet?

for (int index = 1; index < n; index *= 2) {
    int counter = 0;
    while (counter < n) {
       counter++;
    }
}

Determine its best and worst case runtime in the Big-Theta notation as a function of n.

I think the worst case is n*log(n), but I am not sure about the best case.

algorithmtime-complexitybig-o


Solution 1:[1]

The time complexity is indeed O(?log?), but there is no notion of best or worst.

Such notions of best or worst only play a role when there is some variation possible for a given ?. For instance, sorting algorithms get their time complexity expressed in the size of the input, but then there is still some variation in the way the input is ordered (is it already sorted? Is it sorted in reverse? ...etc).

In this problem, there is only ? as input, nothing else, and so the time complexity is what it is -- no best, no worst.

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 trincot

Related Questions