Complexity of the script

user_17995845 0
Viewed 72

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)
complexity-theory time-complexity algorithm python
1 Answers

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.
user_175561720
Related