Complexity of the following algorithm

Question

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
  }
 }
}

The answer depends on whether the `k=i` at the start of the inner loop is a typo of `k=1` or your professor trying to trick you. — manveti, Dec 20 '18 at 00:01
Choosing a few small values for `n` and printing `k` where the `//code` comment is should give you some insight into how those loops work. — user3386109, Dec 20 '18 at 00:02
Possible duplicate of [How to find time complexity of an algorithm](https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm) — Prune, Dec 20 '18 at 01:53
Welcome to StackOverflow. Please read and follow the posting guidelines in the help documentation, as suggested when you created this account. [On topic](http://stackoverflow.com/help/on-topic), [how to ask](http://stackoverflow.com/help/how-to-ask), and [... the perfect question](https://codeblog.jonskeet.uk/2010/08/29/writing-the-perfect-question/) apply here. We expect you to carry out your due diligence before posting; there are quite a few previous questions that show you how to attack big-**O** determinations. — Prune, Dec 20 '18 at 01:54

Kenpachi Zaraki · Accepted Answer · 2018-12-20T09:17:33.667

Since your k starts with "i" and goes upto "j",your worst case time complexity is O(n²). 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(n²) 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(n²).

Complexity of the following algorithm

1 Answers1