I am trying to find a pair (x,y) in A such that x-y = 0 (mod n) where inputs are a positive integer n, a set A of m nonnegative integers and m > n. To run the code below I took an m and n just for the sake of running an example.

Below is the script I have written.

What is the run time complexity in terms of n and m? --> Would it be O(N)? The main loop runs as much as the length of A, which is of length m. I suppose the question is asking me to discuss in terms of m and n, but I am not sure what there is to say about n?

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)

CodePudding user response：

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.