What is the time complexity of this code?
1 min readMay 8, 2021
for(i= n ; i > 0; i++){
for(j = 0; j<n;j*2){
cout<<i;
}
}
TLDR
O(nlog(n))
Further Explained
In this code, we have nested for loops but the inner loop is using multiplication as its incrementation. The inner loop keeps doubling j until it is less than n and the number of times we can double a number until it is less than n is log(n), so the inner loop time complexity will be around O(logn). The outer loop will just be O(n). This makes the total time complexity O(nlog(n)).
More Reading
