-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

  • What is the purpose of the code? – JacquesB Jan 24 at 16:07
  • this is just a small chunk of a greedy code to generate new sequence. – Farah Amawi Jan 27 at 12:25
  • Why x for i, x in enumerate(arr) and not x for x in arr? – Caleth May 15 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).

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

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