Это неверно. f (n) = тета (g (n)) тогда и только тогда, когда оба f (n) = O (g (n)) и g (n) = O (f (n)). Это правда, что f (n) = O (g (n)). Покажем, что это не тот случай, когда g (n) = O (f (n)).
Предположим, что g (n) = O (f (n)). Тогда существует положительная действительная постоянная c и положительное натуральное число n0, такое что для всех n> n0, g (n) <= c * f (n). Для наших функций это подразумевает n ^ n <= c * 4 ^ n. Если мы возьмем nth root обеих сторон этого неравенства, мы получим n <= 4c ^ (1 / n). Мы можем свободно предполагать c> = 1 и n0> =, поскольку, если мы найдем меньшее значение, которое сработает, будет работать и большее значение. Для всех c> 1 и n> 1 4c ^ (1 / n) строго меньше 4 c. Но тогда, если мы выберем n> 4 c, неравенство будет ложным. Таким образом, не может быть n0 такого, что для всех n хотя бы n0 условие выполняется. Это противоречие; наше первоначальное предположение опровергнуто.