-1

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

3
  • What is the purpose of the code?
    – JacquesB
    Jan 24 '19 at 16:07
  • this is just a small chunk of a greedy code to generate new sequence. 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
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).

3
  • 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 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?!! Jan 24 '19 at 14:16
  • @FarahAmawi That's how big O works. Doesn't mater how big or small constant factors are. Jan 25 '19 at 2:05

Not the answer you're looking for? Browse other questions tagged or ask your own question.