сложность времени

Question

Привет У меня есть вопрос, который:

считают, у меня есть T(n) = m * n^2 (n<m) это правильно написать T(n) = O(m)?потому что я написал T(n) = m*n*n Так как n<m у нас есть T(n) = O(m) спасибо

Answer 1

Я считаю, что в этом случае T (n) = O (n ^ 2)

Формальное определение big-O:

f (x) = O (g (x)) тогда и только тогда, когда существует положительное действительное число M и действительное число x0 такое, что | f (x) | ≤ M | g (x) | для всех х> х0.

В вашем случае T (n) всегда будет меньше или равно m (n ^ 2).

Answer 2

Нет, лучшее, что вы можете сделать, это написать T(n,m) = O(m^3).n < m - это очень слабое состояние и в основном дает вам n in O(m).Например, n всегда может быть m-1.

Редактировать: Мой первый ответ был неточным, поскольку T была только функцией от n.Если m постоянно, ответ остается в силе, но O (m ^ 3) равно O (1).