Is Time complexity O(n) or O(n^2)?

I feel that the time complexity of this js function I wrote is O(n) but at the same time it feels like its O(n^2). What’s the correct time complexity? The function is supposed to find the last index of the first duplicate item found. For example in the first example, 1 was found at index 0 and 1 was also found at index 6. So the result would be 6 because thats the last index of the first duplicate values in that array. If no duplicates found then we return -1.

// [1, 2, 4, 5, 2, 3, 1] --> output: 6
// [1, 1, 3, 2, 4] --> output: 1
// [1, 2, 3, 4, 5, 6] --> output: -1(not found)
// It can be in any order, just need to find the last index of the first duplicate value thats there

const findFirstDuplicateIndex = (arr) => {
    let ptr1 = 0
    let ptr2 = 1   
    while (ptr1 < arr.length - 1) { // O(n)
        if(arr[ptr1] === arr[ptr2]) {
            return ptr2 + 1
        } else {
            ptr2++ 
        }
        if (ptr2 === arr.length - 1) {ptr1++; ptr2 = ptr1 + 1}
    }
   return -1
}

>Solution :

The time complexity of your code is O(n^2).

Your code is another version of two nested loops.

if (ptr2 === arr.length - 1) {ptr1++; ptr2 = ptr1 + 1}

This code is equal to adding a nesting loop i.e

for(ptr2 = ptr1+1; ptr2 < arr.length; ; ++ptr2)

If we rewrite your code with two nested for loops, we have

const findFirstDuplicateIndex = (arr) => {
    for(let ptr1=0; ptr1 < arr.length - 1; ++ptr1) {
      for(let ptr2=ptr1+1; ptr2 < arr.length; ++ptr2){
        if(arr[ptr1] === arr[ptr2]) {
            return ptr2
        }
      }
    }
    return -1;
}

Now,

For the 1st iteration: the inner loop will cost N-1.
For the 2nd iteration: the inner loop will cost N-2.
For the 3rd iteration: the inner loop will cost N-3.
........................
........................
For the (N-1)th iteration: the inner loop will cost 1.

So, the total time complexity is the sum of the cost which is

(N-1) + (N-2) + (N-3) + . . . . + 1

which is an arithmetic series and by using the arithmetic sum formula we have

(N-1) + (N-2) + (N-3) + . . . . + 1 = (N-1)*(N-2)/2 = O(N^2)

Hence, the time complexity of your code is O(n^2).