Анализ алгоритма с большой тэтой

Question

Я должен сказать, сложность времени для этих трех алгоритмов.Возможно ли, что кто-то может увидеть, верны ли они?

Я также не уверен, как найти тэту?

Я знаю, что тэта - это среднее значение от Big-O и Omega.Но я чувствую, что это в основном то же самое, когда дело доходит до анализа кода и написания его в формате Big-O.

Answer 1

первый кажется правильным с нижеследующим объяснением, определение Θ обозначения как ниже

Θ(g(n)) = {f(n) : there exists c1,c2,n0 such that
                 0 <= c1*g(n) <= f(n) <= c2*g(n) given c1,c2,n0 > 0}

Здесь, в 1-м фрагменте, мы должны искать f (n), который равен

f(n)= n/3 + n/5 = 8/15*n

Чтобы найти g (n), если мы предположим, что c1 = 0,5, c2 = 2, n0 = 15 (поскольку делится на 3 и 5), то ниже будут случаи

when n=15, 0<=c1g(n)<=f(n)<=c2g(n)  =>  0<=c1g(n)<=1*8/15*15<=c2g(n)  =>  0<=0.5*g(n)<=8<=2*g(n)
when n=30 0<=0.5g(n)<=16<=2g(n)
when n=90 0<=0.5g(n)<=48<=2g(n) ...so on

when n=17 0<=0.5g(n)<=9<=2g(n)
when n=20 0<=0.5g(n)<=10<=2g(n)

Следовательно, g (n)= n кажется подходящим выбором, и, поскольку мы можем продемонстрировать одну комбинацию c1, c2 и n0, которая демонстрирует правильность определения, g (n) = n является приемлемым ответом.