-1

Can you explain to me how can I find the time complexity of these algorithms?

(1)
    for i←1 to n
        for j←1 to i
            for k ← j to i
                print(i+j+k)

(2)
    for i=1 to n
    {
        for j = 1 to i
        {
            for k = 1 to j
                print k
        k = 2
        while k < i
            k = k^2
        }
    }
David
  • 4,665
  • 4
  • 34
  • 60
Golan Kiviti
  • 3,895
  • 7
  • 38
  • 63

1 Answers1

0

You find it quite easily. You look at the innermost loop and figure out how often it will be iterated, depending on the circumstances (in this case depending on the values of i and j).

Then you look at the second loop and figure out what values i and j will have in the inner loop, and use that to calculate how often the innermost statement is executed, depending on the circumstances of the middle loop (in this case depending on i).

And then you do the same with the outer loop. Just use your brain, that's how you find it.

Just write: "Depending on the values of i and j, the innermost loop will execute ... times". "Depending on the value of i, the second loop will execute with the values j = .. to .. which means the innermost loop will execute ... times and adding this up for all iterations of the middle loop, the inner loop will execute ... times, depending on the value of i". "The outermost loop will execute with the values i = .. to .. which means that in each iteration of the outer loop, the inner loop executes ... times. Adding this up means the inner loop executes ... times".

gnasher729
  • 51,477
  • 5
  • 75
  • 98
  • well, the maximum value of i is N, and the minimum value of j is 1, so when j is 1 and i is N the most inner loop will be iterated N times, so the answer is N^3? – Golan Kiviti Feb 17 '15 at 14:21
  • You are guessing. You looked at two bits of the code and ignored the rest. – gnasher729 Feb 17 '15 at 14:25