Give the asymptotic complexity of each of the following functions in simplest te

Question

Give the asymptotic complexity of each of the following functions in simplest terms. Your solution should have the form Theta(n^alpha) or Theta((log_mu (n))^beta) or Theta(n^alpha(log_mu(n))^beta) or Theta(gamma^delta n) or Theta((log_mu (n))^beta) or Theta(n^alpha (log_mu (n)^beta)) or Theta (gamma^delta n) or Theta (1) where alpha, beta, gamma, delta, mu are constants. (m) f_m(n) = 3 times 3^n + 4 + 4 times 6^n + 2; (n) f_n(n) = (n - 1) log_10 (6n^3 - 4n^2 - 2n - 1) + 3n + 8; (o) f_o(n) = Squareroot 10 log_9 (n) + 9n + 21; (p) f_p(n) = 3^n + 9^n + 12^n; (q) f_q(n) = (8n^2 + n^2 + 6) times (n^3 + 8n + 3) times (n^2 - 2); (r) f_r(n) = 3 times 7^n + 3 + 14 times 7^n + 6; (s) f_s(n) = 4^8n + 5 times 8^n; (t) f_t(n) = 2 log_9 (6^n + n^6 + 6); (u) f_u(n) = 8n^7 + 3^n + 2 + 6^n + 7; (v) f_v(n) = 5 times 5^log_5 (5n^5 + 5n^3);

Explanation / Answer

(According to Chegg policy, only four subquestions will be answered. Please post the remaining in another question)

(s) fs(n) = 48n + 5*8n

=> fs(n) = (48)n + 5*8n

We have 8 < 48

For n > 1

=> 8n < (48)n

=> 5*8n < 5(48)n

=> (48)n + 5*8n < (48)n + 5(48)n

=> (48)n + 5*8n < 6 (48)n

=> (48)n < (48)n + 5*8n < 6 (48)n

=> (48)n < fs(n) < 6 (48)n

=> fs(n) = (48n)

(p) fp(n) = 3n + 9n + 12n

For n > 1,

3n + 9n + 12n > 12n

and 3n + 9n + 12n < 12n + 12n + 12n

=> 12n < 3n + 9n + 12n < 3*12n

=> 12n < fp(n) < 3*12n

=> fp(n) = (12n)

(v) fv(n) = 5*5log5(5n^5+5n^3)

=> fv(n) = 5log5(5n^5+5n^3)+1

=> fv(n) = 5log5(5n^5+5n^3)+log5 5

=> fv(n) = 5log5(5n^5+5n^3)*5

=> fv(n) = 5log5(25n^5+25n^3)

=> fv(n) = 25n5+25n3

=> fv(n) = 25(n5 + n3)

We have for n>1, 25n5< 25(n5 + n3) < 25(n5 + n5)

=>25n5 < 25(n5 + n3) < 50n5

=> 25n5 < fv(n) < 50n5

=> fv(n) = (n5)

(m) fm(n) = 3*3n+4 + 4*6n+2

=> fm(n) = 3*3n*34 + 4*6n*62

=> fm(n) = 243*3n + 144*6n

For n >1, we have

144*6n < 243*3n + 144*6n < 243*6n + 144*6n

=> 144*6n < 243*3n + 144*6n < 387*6n

=> 144*6n < fm(n) < 387*6n

=> fm(n) = (6n)

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.