-1

The following algorithm takes in an array, arr (which takes positive and negative values), and a number, target, and finds all pairs of integers in the array that add to give the target number.

def pairs(arr, target):
    for i in range(len(arr) - 1):
        for j in range(i+1 ,len(arr)):
            if arr[i] + arr[j] == target:
                print(arr[i], arr[j])

My question is what is the time complexity of this algorithm? I would think it is somewhere between $O(n)$ and $O(n^2)$ as the first for loop is $O(n)$ but the second for loop is not quite $O(n)$ because it doesn't go through the whole array each time. The other steps are $O(1)$.

idk31909310
  • 99
  • 1
    The number of iterations of the second loop is still proportional to n. In fact, you can calculate the exact number of iterations for the whole function. That will give you the answer. – mkrieger1 Aug 23 '23 at 20:15
  • Voting to close since this is a theoretical computer science / mathematics question, and not a specific programming question. But in any case, do note that `O(0.000000000001 n)` is still `O(n)`. `O(n)` means "bounded above by a linear function of n for sufficiently large n", not "does something exactly n times" – Brian61354270 Aug 23 '23 at 20:17

0 Answers0