patternMinor
What is the time complexity of this function?
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
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.
For being more clear take a look at this question.
Context
StackExchange Computer Science Q#2487, answer score: 5
Revisions (0)
No revisions yet.