CODEWITHSUNDEEP
algorithmtime-complexitycomplexity-theory
alex
alex

Reputation: 83

Complexity of the following algorithm

I'm trying to find the complexity of the following algorithm:

for(i=1;i<=n;i++){
 for(j=1;j<=i;j++){
  for(k=i;k<=j;k++){
    //code
  }
 }
}

Upvotes: 0

Views: 145

Answers (1)

Kenpachi Zaraki
Kenpachi Zaraki

Reputation: 404

Since your k starts with "i" and goes upto "j",your worst case time complexity is O(n2). Lets take an example and see. For i=4, j goes from 1 to 4 and k runs only one time for each value of j (except for j=4 which runs exactly 2 times).Therefore for each value of j,the inner loop runs in O(1) time. The outer two loops take O(n2) time. Also, taking into account that your (//code) inside the innermost loop runs in O(1) time. Therefore, time complexity for this algorithm is O(n2).

Upvotes: 2

Related Questions