Используя определение \Theta, есть две константы c1 и c2, такие что для каждого n мы имеем c1 * g(n) < f(n) < c2 * g(n).Поскольку log является возрастающей функцией, мы можем применить log к каждой стороне неравенства: log(c1) + log(g(n)) < log(f(n)) < log(c2) + log(g(n)).Следовательно, основываясь на определении \Theta(n), у нас есть log(f(n)) = \Theta(log(g(n)), и вы не можете найти контрпример для этого случая.