CODEWITHSUNDEEP
pythonalgorithmtime-complexity
Kumar Sanu
Kumar Sanu

Reputation: 226

Why complexity of first code is more than that of second one?

Append has constant time complexity O(1). Extend has O(n) complexity as in my case k(the number of elements to be added)=n-1. Insert and del both have O(n) time complexity. Then why first code is taking longer time than second one?
1. First piece of code

def circularArrayRotation(a,n, queries):      
  for _ in range(n):
      arr=[]
      arr.append(a[-1])
      arr.extend(a[0:-1])
      a=arr          
  for j in queries:
      yield a[j]
  1. Second piece of code
def circularArrayRotation(a, n, queries):
    for _ in range(n):
        a.insert(0, a[-1])
        del a[-1]
    for j in queries:
        yield a[j]

Upvotes: 0

Views: 70

Answers (1)

Mykhailo Bykhovtsev
Mykhailo Bykhovtsev

Reputation: 512

I am not 100% sure. But My assumption is because in first code you call arr.extend(a[0:-1]) which has to make a temporary sub-list. The creation of sub-list will take extra time. I would assume the creation of sub-list would be something like O(M) where M is size of sublist.

Edit: Plus in Big O, you have O(2N) = O(N). But in practice that still affects performance, just not as significant as anything else.

Upvotes: 1

Related Questions