0
Time Complexity (Emergency Help)
Solved: True 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))
2 Réponses
0
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.
0
`ᴴᵗᵗየ thanks about your help, too be honest I think a lot about it and search more and more to find its answer, finally I found that the time complexity of this code is:
O(n^2)
XD