Асимптотика c отношение роста между 2 ^ n и 2 ^ (n / 2)

Question

Вот этот вопрос, который я решаю, где f(n) = 2^n g(n) = 2^(n/2) f(n) = ?(g(n)) Я нашел много ответов как Ω и ω. Но разве это не должно быть f(n) = θ(g(n))? Поскольку константа не должна влиять на рост функции?

Answer 1

f(n) = θ(g(n)) тогда и только тогда, когда f(n) = Ω(g(n)) и f(n) = O(g(n)), но мы видим, что f(n) = O(g(n)) просто не выполняется, как описано ниже.

O (g (n)) = {f (n): существуют положительные константы c и n0 такие, что 0 <= f (n) <= c g (n) для всех n> = n0}

2 ^ n <= c 2 ^ (n / 2) приведет к 2 ^ (n / 2) <= c, и мы не можем найдите такое n0, чтобы выполнить приведенное выше определение. </p>

n = np.linspace(1, 10)
plt.plot(n, 2 ** n, label="2 ** n")
plt.plot(n, 2 ** (n/2), label="2 ** (n/2)")
plt.legend(loc='upper left')
plt.show()

Ссылка: CLRS