Time Complexity (Emergency Help)

Question

for(int i = 0 ; i < n ; i++){
for(int j{1} ; j < n ; j *= 2){
for(int k{j} ; k > 0 ; k--){
cout << "Lost\n";
}
}
}

why Time Complexity of above nested loop is:

O(nlog(n)) + O(n) : O(nlog(n))

Answer 1

The time complexity of the provided nested loop can be broken down into two main parts e.g.

The innermost loop runs in O(j) time, where j ranges from j to 1, halving at each step. Hence, the second loop runs in O(log(j)) time.

The outermost loop runs in O(n) time. Combining these, we get O(nlog(n)) + O(n) complexity for the entire nested loop. The log(j) is equivalent to log(n) in this case, leading to O(nlog(n)) + O(n) time complexity.