Правильно ли я посчитал асимптотическую сложность алгоритма?

Question

void MaxValueInArray()
{
    Random rand = new Random(); // O(1)
    int[] array = new int[rand.Next(0, 10)]; // O(1)
    int lagerst = 0; //O(1)
    for (int i = 0; i < array.Length; i++) // заполнение массива  0(N)
    {
        array[i] = rand.Next(0, 100);
        Console.Write($"{array[i]} ");
    }

    for (int i = 0; i < array.Length; i++) //O(N)
    {
        if (array[i] > lagerst)
        {
            lagerst = array[i];
        }
    }

    Console.WriteLine($"\nНаибольшее число: {lagerst}"); //O(1)
    //Сложность алгоритма O(1+1+N+N+1) = O(3+2N)
}

Answer 1

Неверно, т.к. вкратце без подробностей в нотации O не учитываются константы.
Т.е. O(2n) == O(n), O(3) == O(1), O(3+2N) == O(N).

Answer 2

По-другому ещё можно сказать, что финальный подсчёт должен вестись взятием максимальной сложности среди частей алгоритма:

max(O(1), O(1), O(N), O(N), O(1)) -> O(N)

БЛОГ НА HUSL

Правильно ли я посчитал асимптотическую сложность алгоритма?

Ответы (2 шт):