Согласно моей информации, мы говорим, что f (n) есть Ω (g (n)), если g (n) есть O (f (n)), то есть существует реальная постоянная c> 0 ицелочисленная константа n_0> = 1 такая, что
f(n) >= cg(n), for n >= n_0
, например,
3nlogn + 4n + 5logn is Ω(nlogn)
Тогда, согласно определению, f(n) = 3nlogn + 4n + 5logn и g(n) = nlogn, значение c должно быть 1, правильно? Но тогда каждый вопрос, который мы решаем, будет иметь c = 1. С другой стороны, если мы введем c = 3 (коэффициент g (n)), даст ли он правильный ответ? Как найти правильное значение c?