State the asymptotic complexity of each of the following functions in simplest t

Question

State the asymptotic complexity of each of the following functions in simplest terms, using theta(f(n)) ("theta") notation. You do not need to provide any justification or proof. F_a(n) = n^4 + 2n^3 + 10n^2 + .5n - 64 f_b(n) = 1024 middot Ign + n f_c(n) = Squareroot n^2 + 8n +8 f_d(n) = 2^n + 4^n + 8^n f_e(n) = 4(n + 11 ) lg(n^2 + n) + 10n f_f(n) = Squareroot lg (n^2) + n + 18 f_g(n) = 2^12 + 3^3 middot 6 lg(88888) f_h(n) = 17 lg(3n + 15) + 22lg(5n + 9) f_i(n) = 7n^0.6 + 3 Squareroot n f_j (n) = 3 lg(n^3 + n^2) + 4n^0.4 Provide a "big oh" run-time analysis for each of the following. When a value of "n" is used, it is the size of the input. You may assume max() and min() are constant-time in-line functions. void problem_2a() { cin >> rows >> cols; n = rows * cols; step = n; while (step > 1) for (i = 0; i

Explanation / Answer

1.
(a) O(n4) [Since n4 is the highest polynomial among all in fa(n)]
(b) O(n) [Since n is asymptotically larger than log n ]
(c) O(n) [Since Sqrt(n2) Is n and Inside it we have one more n again Sqrt(n). Since n > Sqrt(n)]
(d) O(23n ) [ Convert all to 2n 22n 23n   ]
(e)O(nlgn) [lg(n2) is 2lgn and outside we have 4(n+11) , so nlgn > n]
(f) O(n) [Sqrt (l2gn) and n , At any time n > Sqrt (l2gn)]
(g)O(1) [All are constants]
(h) O(lgn) [Both are log n]
(i) O(n0.6)  [n0.6 > n0.5 ]
(j) O(n0.4)  [n0.4 > log x ]


2(a) cin >> rows >> cols

while(step >1 ) --->runs for row*cols time i.e n times
   for (i till row )
       for (i till row ) --> runs for  row*cols time i.e n times
--step

So overall time compexity is O(n2) . If we write in terms of rows and columns its is O(row2 * col2))

2(b) for (i till n2 )
   b[i] . //Runs for O(n2)
Then there are three loops one inside the other
for (i till n )
       for (j till n )
     for (k till n )
   //Runs for O(n3)
So overall time Complexity is n2 + n3 = O(n3)
So overall time Complexity of 2(b) is O(n3)



Thanks, Let me know if there is anything.

     

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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