Как рассчитать сложность времени в Большой тэте

Question

Я пытаюсь вычислить сложность времени в Большой тэте.Пожалуйста, помогите мне с этой проблемой.

Q.Есть две функции, sub1 и sub2 , которые имеют временную сложность θ (4 ^ n), θ (n ^ 4 * log (n)) для каждой.Если это так, выясните следующие два вопроса.

Q1.for(i=1; i<n; i*=4) sub1();

Q2.for(i=1; i<n; i+=4) for(j=1; j<n; j*=4) { sub1(); sub2(); sub1(); sub2(); }

Answer 1

S1.Функция sub1 вызывается (log_4 (n)) раз.Таким образом, общая сложность времени составляет: θ (4 ^ n log_4 (n)) = θ (4 ^ n log (n))

S2.Первый цикл происходит n / 4 раза, а второй log_4 (n) раз.Каждый шаг занимает 2 * θ (4 ^ n) + 2 * θ (n ^ 4 * log (n)) = θ (4 ^ n) по определению θ.Таким образом, общее время составляет: n / 4 * log_4 (n) * θ (4 ^ n) = θ (n) * θ (log (n)) * θ (4 ^ n) = θ (n * 4 ^ n* log (n)), снова по определению θ.