Ситуация станет еще интересней, если мы введем следующее дополнение, что принцесса будет сравнивать претендента со всеми, которые уже были, то получается:
N*N-1=N
2-N, но асимптотический анализ нам разрешает отбросить как член младшего порядка N, таким образом мы приходим к выводу, что в этом случае производительность становится уже O(n
2). Отсюда вывод: девушки соритруйте своих избранников перед смотринами, а потом применяйте метод бинарного поиска, который при каждом проходе по всему множеству позволяет его уполовинить
