Быстрый Большой О, расчет

Question

Я рассматриваю обозначение Big Oh.Существует ли такая вещь, как функция большого порядка: O (n * (n / 2))?Я просто предположил, что это будет просто O (n ^ 2), но эти заметки говорят по-другому (не мои заметки).Примечания относятся к этому коду:

for(int i = 0; i < x; i++)
{
    for(int j = 0; j < x/2; j++)
    {
        halfsum += a[i][j];
    }
}

Answer 1

Вы отбрасываете коэффициент так технически, что все еще O (n ^ 2).Другими словами O ((n ^ 2) / 2) = O (n ^ 2).

Answer 2

В нотации big-O верно, что O (n ^ 2) = O (n ^ 2/2), поэтому, конечно, O (n ^ 2/2) существует, констатировать константу просто бессмысленно так зачем? Не то чтобы это не правильно, просто бессмысленно.

Это похоже на простую математику 6-го класса: X = X * 1. Нет смысла записывать умножение на 1, но это не ошибочно.