Time Complexity of the algorithm - for loop

Question

for i := 1 to n
    for j : = 1 to i
         for k := 1 to 18

              BEEP

         next k
     next j
next i

Which of the following are true?

f(n) is O(n^3)

f(n) is Θ (n^2)

f(n) is Ω (n^3)

Welcome to Stackoverflow. I get the distinct feeling, that this is some sort of homework that you want to get done/solved by the community. At least show some effort or argue between the solutions. — jhoepken, Nov 16 '19 at 08:08

score 2 · Answer 1 · answered Nov 16 '19 at 08:18

If you analize the three loops, from external one to the nested one, the following is each one time complexity (Big O):

O(n) Because the number of iterations is proportional to n.
O(n) Because the average of lenth of this loop is n/2 because this is de average of 1,2,3,..n.
O(1) Because this is a constant length loop (it does not depend on n). So, if you multiply (because the are nested) this three loops time compexity, you get:

O(n) * O(n) * O(1) -> O(n^2)

1 Answers1