HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

What is the time complexity of this function?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
thisthewhatfunctiontimecomplexity

Problem

This is an example in my lecture notes.
Is this function with time complexity $O(n \log n)$?.
Because the worst case is the funtion goes into else branch, and 2 nested loops with time complexity of $\log n$ and $n$, so it is $O(n \log n)$. Am I right?

int j = 3;
int k = j * n / 345;
if(k > 100){
    System.out.println("k: " + k);
}else{
    for(int i=1; i<n; i*=2){
        for(int j=0; j<i; j++){
            k++;
        }
    }
}

Solution

Time complexity of mentioned algorithm is $O(1)$, because for $K>100$ you have a constant operation (println), and you know: $j=3,k = 3 \cdot n / 345 \implies 100 = 3\cdot n / 345 \implies n=11500$, means for $n\ge 11500$ your algorithm has a constant running time (also other part is constant, because just for $n<11500$ will be called).

For being more clear take a look at this question.

Context

StackExchange Computer Science Q#2487, answer score: 5

Revisions (0)

No revisions yet.