time complexity for 3 foor loops different leangth

Question

I have this method

arr // input


new_ seq = []

for i in arr:
  new_seq.append(i)
  __new_seq = [x for i, x in enumerate(arr) if x not in new_seq]
  for j in __new_seq:
      new_seq.append(j)
      __new_seq = [x for i, x in enumerate(arr) if x not in new_seq]
      for k in __new_seq:
          new_seq.append(k)

How to calculate the time complexity for this method Please note that each loop has a smaller length than the one before

this is just a small chunk of a greedy code to generate new sequence. — Farah Amawi, Jan 27 '19 at 12:25
Why `x for i, x in enumerate(arr)` and not `x for x in arr`? — Caleth, May 15 '19 at 16:43

score 2 · Accepted Answer · answered Jan 24 '19 at 14:01

2

Ordinarily, a loop that executes only part of the time counts as a normal loop - complexity analysis ignores constant factors. That would make it cubic time complexity.

In this case, though, the inner loops never execute, so it should be quadratic time (the middle loop body never executes, but you still spend time iterating the second for...in).

answered Jan 24 '19 at 14:01

Kilian Foth

107,706
45
295
310

1

Please see the updated code. The first loop takes all the arr elements O(n) The second and the third loop takes all the elements that has not been added to the new_seq this is not O(n)^3 .... I think its less than that – Farah Amawi Jan 24 '19 at 14:12
Just to clarify your answer => time complexity for this code is O(n) ? Regardless the time needed for the second the the third loop?!! – Farah Amawi Jan 24 '19 at 14:16
@FarahAmawi That's how big O works. Doesn't mater how big or small constant factors are. – candied_orange Jan 25 '19 at 02:05

time complexity for 3 foor loops different leangth

1 Answers1