Я понимаю, что O (N) по существу равно O (cN), где c = 'некоторая константа'. Но если N = c. Не делает ли это O (N)^2. Сохраняется ли это с увеличением с или существует какой-то формальный предел.Почему O (n) равно O (2n)
Если N = c затем c не является постоянным. Поэтому это никогда не бывает.
O (n) означает, что время выполнения алгоритма линейно увеличивается с размером ввода. Если вы удвоите размер ввода, вы удвоите время выполнения. Если вы в три раза увеличиваете размер ввода, вы утроёте время выполнения. И так далее. Таким образом, график является прямой линией.
O (n^2) означает, что время выполнения алгоритма увеличивается квадратично с размером ввода. Если вы удвоите размер ввода, вы увеличите время выполнения в четыре раза. Это плохо. График типа циклов и становится действительно высоким очень быстро.
С O (2n) вы увеличили наклон линии, но она по-прежнему является линией. Поскольку он линейный, он «сводится» к O (n).
Надеюсь, что помогает.