Asymptotic Complexity Comparisons
(a) Order the following functions so that for all i,j, if fi comes before fj in the order then fi = O(fj). Do not justify your answers.
As an answer you may just write the functions as a list, e.g. f8,f9,f1,...
(b) In each of the following, indicate whether f = O(g), f = Ω(g), or both (in which case f = Θ(g)). Briefly justify each of your answers. Recall that in terms of asymptotic growth rate, logarithmic < polynomial < exponential.
Computing Factorials
Consider the problem of computing N! = 1 × 2 × ··· × N.
(a) N is logN bits long (this is how many bits are needed to store a number the size of N). Find an f(N) so that N! is Θ(f(N))) bits long. Simplify your answer as much as possible, and give an argument for why it is true.
Note: You may not use Stirling’s formula.
(b) Give a simple (naive) algorithm to compute N!. You may assume that multiplying two bits together (e.g. 0 × 0,0 × 1) takes 1 unit of time.
Please give both the algorithm description and runtime analysis.
Polynomial Evaluation
Given coefficients a0,...,an ∈ N, consider the polynomial:
n
p(x) = Xakxk
k=0
For this problem, assume that addition and multiplication of two natural numbers takes only O(1) time (regardless of how large they are).
(a) Describe a naive algorithm that, given [a0,...,an] and x, computes p(x). Give an analysis of its runtime as a function of the degree of the polynomial n.
(b) As an alternative, we can compute the following expression:
p(x) = a0 + x(a1 + x(a2 + ... + x(an−1 + x · an)...))
Describe and analyze an algorithm that evaluates the polynomial using the above expression. The runtime should be a function of n as well.
Give a 3-part solution as described in the homework guidelines.
