What is the worst case running time in Big-Oh notation

user_14074043 0
Viewed 257

What is the worst case running time in Big-Oh notation for the function below?Can someone please explain why? Thanks.

test{
int counter = 0;

    for int(i=0; i<5000;++i){
    counter += i;
    
        for(j=0;j<n;++j){
        ...
        }
    
        for(k=0;k<i;++k){
        ...
        }
    
    }

}
time-complexity algorithm
3 Answers

5000 is a constant, so it is not important. The only important thing is the for loop with n in it, so this is O(n).

user_9274930

Big-O notation tells you that the algorythm scales the same or slower then the function.

  • O(N) means that if you have 10 times more input data it will take 10 times longer or less.

  • O(N^2) means at 10 times more data its 100 times longer or less.

Your input is n, i is on a costant loop. Therefore your complexity is O(n) as n is in a for loop, so it scales linearly, unless you use n in another loop somewhere.

You might have noticed the "or less", you might argue that all O(N) algorythms therefore are also O(N^2) or worse, and this is technically true, however not helpful. This is why you'd pick the fastest Big-O notation to indicate a good approximation.

user_54591010

Big-O notation talks about the running time proportional to n. Here, all loops repeat the same number of times except for one loop with n inside. Therefore, only the inner loops running time changes when n changes, so it is O(n).

user_134574100
Related