CODEWITHSUNDEEP
pythonalgorithmtime-complexitycomplexity-theory
nich
nich

Reputation: 35

Complexity of the script

I am trying to find a pair (x,y) in A such that x-y = 0 (mod n)

Below is the script I have written.

What would be the run time complexity if n is a constant? --> So, this is asked but isn't n a constant anyway? I am a bit confused, the question says "inputs are a positive integer n..."

def find_equal_pair_mod_n(n, A):
  assert len(A) > n

  X = [-1] * n
  print(X)

  for i in range(len(A)-1,-1,-1) :  #loop backwards
    print(i)
    a = A[i]
    print(a)
    print(len(A))
    A.pop(i)
    r = a % n

    if X[r] == -1:
      X[r] = a
    else:
     return(X[r], a)

Upvotes: 2

Views: 160

Answers (1)

Oleksii Tambovtsev
Oleksii Tambovtsev

Reputation: 2844

Short answer

  1. "What is the run time complexity in terms of n and m?". The correct answer is O(n).
  2. "What would be the run time complexity if n is a constant?". The correct answer is O(1).

Explanation

  1. When you iterate over your loop, you can't do more than n + 1 iterations, because there are only n different remainders when divided by n. So you definitely find the answer in n + 1 or fewer iterations.
  2. If n is constant, you are still need n + 1 or fewer iterations to find the answer, so you need a constant time to solve your problem.

Upvotes: 1

Related Questions