1. let f(n) = 2 and g(n) = n. Asymptotically, which one grows faster? Prove it....

Transcribed Image Text:

1. let f(n) = 2 and g(n) = n. Asymptotically, which one grows faster? Prove it. 2. Use induction to prove that the following equation is true for every positive integer n. Show all three steps. 3. Given the following code: a and b are integers k (k + 1) = k=1 n is the size of the input basic op is a basic operation myfun (a, b) { if (a == b) { n(n + 1)(n+2) 3 for (x 1 to n+n) basic op; for (x 1 to n*n) basic op; } else { for (x = 1 to 10) for (y = 1 to x) basic op; } } a) What is the worst case running time, i.e., f(n)=0(?) Show your work/calculation for determining this? b) What is the best case running time, i.e., f(n) = 2 (?) Show your work/calculation for determining this? c) Can we describe the average case running time, i.e., f(n) = (?)? If yes, what is it? If no, explain why you can't. 1. let f(n) = 2 and g(n) = n. Asymptotically, which one grows faster? Prove it. 2. Use induction to prove that the following equation is true for every positive integer n. Show all three steps. 3. Given the following code: a and b are integers k (k + 1) = k=1 n is the size of the input basic op is a basic operation myfun (a, b) { if (a == b) { n(n + 1)(n+2) 3 for (x 1 to n+n) basic op; for (x 1 to n*n) basic op; } else { for (x = 1 to 10) for (y = 1 to x) basic op; } } a) What is the worst case running time, i.e., f(n)=0(?) Show your work/calculation for determining this? b) What is the best case running time, i.e., f(n) = 2 (?) Show your work/calculation for determining this? c) Can we describe the average case running time, i.e., f(n) = (?)? If yes, what is it? If no, explain why you can't.

Answer rating: 100% (QA)

1 To determine which function grows faster asymptotically we need to compare their growth rates as n approaches infinity In this case we are comparing ... View the full answer