Это сложность N или N ^ 2?

Question

Я решал вопрос, в котором я должен создать уникальный массив из отсортированного массива, который может содержать дубликаты элементов.

Я решил решение, используя следующий код:

for (int i = 0; i < sorted.Length - 1; i++)
{
    if (sorted[i] == sorted[i + 1])
    {
        unqiueList.Add(sorted[i]);
        int j = i + 1;
        while (j < sorted.Length)
        {
            if (sorted[i] != sorted[j])
            {
                break;
            }
            j++;
            i++;
        }
    }
    else
    {
        unqiueList.Add(sorted[i]);
    }
}

Теперь я хочу знать сложность этого решения.

Некоторые люди говорят, что это N, но некоторые говорят, что это N ^ 2. Это подсказывает мне, почему бы не задать тот же вопрос для переполнения стека, чтобы лучше его понять.

Answer 1

В худшем случае O(N).

Это немного неприятно, но учитывая тот факт, что i и j увеличиваются на каждой итерации в цикле while, естьв основном нет циклов в цикле.

Алгоритм не допускает больше итераций, чем sorted.Length.

---

Интересно;это указывает на то, что цикл while можно заменить на оператор if (может быть, не простой), но это было бы неплохо.