1. State the asymptotic complexity of each of the following functions in simplest terms, using 0(f(n))...

  

Transcribed Image Text:

1. State the asymptotic complexity of each of the following functions in simplest terms, using 0(f(n)) ("theta") notation. You do not need to provide any justification or proof. [2pts. ea.] (a) fa (n) = n + 2n +10n + .5n - 64 (b) f(n) = 1024 - Ign + n (c) fe(n)= n + 8n +8 (d) fa(n) = 22 +47 +8n (e) fe(n) = 4(n + 11)lg(n + n) + 10n (f) ff(n) = lg(n) +n+18 (g) fg (n) = 22 +3.6lg(88888) (h) f(n) 17lg(3n+15) + 22lg(5n +9) (i) fi(n) = 7n0.6 +3n (i) f(n) = 3lg(n+n) + 4n0.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. [10pts. ea.] 3) Give an 2.a.) void problem_2a() { } cin >> rows >> cols; n = rows * cols; step = n; while (step > 1) for (i = 0; i 1. State the asymptotic complexity of each of the following functions in simplest terms, using 0(f(n)) ("theta") notation. You do not need to provide any justification or proof. [2pts. ea.] (a) fa (n) = n + 2n +10n + .5n - 64 (b) f(n) = 1024 - Ign + n (c) fe(n)= n + 8n +8 (d) fa(n) = 22 +47 +8n (e) fe(n) = 4(n + 11)lg(n + n) + 10n (f) ff(n) = lg(n) +n+18 (g) fg (n) = 22 +3.6lg(88888) (h) f(n) 17lg(3n+15) + 22lg(5n +9) (i) fi(n) = 7n0.6 +3n (i) f(n) = 3lg(n+n) + 4n0.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. [10pts. ea.] 3) Give an 2.a.) void problem_2a() { } cin >> rows >> cols; n = rows * cols; step = n; while (step > 1) for (i = 0; i

Answer rating: 100% (QA)

The image shows a sheet of paper with several questions related to computer science and mathematics ... View the full answer