Интересно, правда ли следующее?
Если f (n) равно O (g (n)) и f (n) также равно Ω (g (n)), это означает f (n) также большой Θ (g (n)) верно? Кроме того, если любое из 2 выше ложно, то f (n) не велико Θ (g (n))?
Если f (n) - это O (g (n)), а f (n) - это также Ω (g (n)), это означает, что f (n) также является большим Θ (g (n)), верно?
Да. Это определение большой тэты.
Кроме того, если любое из 2 выше ложно, то f (n) не велико Θ (g (n))?
Да. Это биекция.
если мы знаем, что f1 (n) - это g (g (n)), а f2 (n) - это Θ (g (n)), значит ли это, что f1 (n) + f2 (n) - это Θ (g (n) )). Почему?
Поскольку f1 (n) приблизительно равно c1 * g (n), а f2 приблизительно равно c2 * g (n), поэтому f1 (n) + f2 (n) приблизительно равно (c1 + c2) * g (n), и поэтому любая линейная комбинация сохранит это соотношение.
Так как big-omega - это нижняя граница, big-O - это верхняя граница, а big-theta - это верхняя и нижняя границы, это само собой разумеется.