I’m working on a Mathematics question and need guidance to help me study.
1. Let f(n) = 2n^3 −n^2 + 10n−7. Prove that f(n) is O(n^3). Show all work.
2. Prove by contradiction that 6^n is not O(2^2n).
3. Suppose that f(n) is O(g(n)). Does it follow that 2^f(n) is O(2^g(n))? Justify your answer.
4. Consider the following pseudocode for an algorithm called “Algorithm,” which reads
procedure Algorithm(a1, a2, …, an: integers)
x := a1
for i := 2 to n
x := x + ai
return x Suppose a list a1,a2,…,an of integers is given as an input.
a) Describe what Algorithm(a1, a2, …, an) returns as output.
b) How many times would the expression x := x + ai be executed?
c) Give a Θ estimate for the runtime of this algorithm.
5. [3 marks] Consider the following pseudocode for an algorithm called “Algorithm,” which reads
procedure Algorithm(a1, a2, …, an: integers)
set L as the empty list
sum := 0
i := 1
while i ≤ n
if ai > sum then append ai to L end if
sum := sum + ai
i := i + 1
return L Suppose a list a1,a2,…,an of integers is given as an input.
a) Describe what Algorithm(a1, a2, …, an) returns as output.
b) How many times would the expression i ≤ n be executed?
c) Give a Θ estimate for the runtime of this algorithm.
Order the answer to view it
