What is the complexity of this code? | Sololearn: Learn to code for FREE!
New course! Every coder should learn Generative AI!
Try a free lesson
+ 8

What is the complexity of this code?

void conundrum (int n) { int i, j, k; int r = 0; for(i=1; i<=n; i++) for (j = i+1; j<= n; j++) for (k=i+j-1; k<= n; k++) r = r+1; }

9th Dec 2017, 11:11 PM
Firas Nassif Makki
Firas Nassif Makki - avatar
5 Answers
+ 9
thank u @Ran 😊
9th Dec 2017, 11:19 PM
Firas Nassif Makki
Firas Nassif Makki - avatar
+ 9
Exactly!
9th Dec 2017, 11:21 PM
Ran Avital
Ran Avital - avatar
+ 8
Worst case scenario : O(n³)
9th Dec 2017, 11:18 PM
Ran Avital
Ran Avital - avatar
+ 7
You're welcome!
9th Dec 2017, 11:19 PM
Ran Avital
Ran Avital - avatar
+ 5
The time complexity of a code is roughly N to the power of the maximum number of nested for loops. Here it is 3, so O(N³)
9th Dec 2017, 11:20 PM
👑 Prometheus 🇸🇬
👑 Prometheus 🇸🇬 - avatar