Computer Science: Big O, Ω, Θ
Read this topicExplanations 1
Problems 5
- Find the smallest kkk such that O(n2+n)=O(nk).O(n^2+n) = O(n^k).O(n2+n)=O(nk).
- Does 5n2+5=θ(n2)?5n^2+5 = \theta(n^2)?5n2+5=θ(n2)?
- Find the smallest aaa such that [∑k=1n(nk)]2=O(an).\left[\sum_{k=1}^{n} \binom{n}{k} \right]^2 = O(a^n).[∑k=1n(kn)]2=O(an).
- Given that a1=2a_1 = 2a1=2, a2=8a_2 = 8a2=8, and an=6an−1+7an−2a_n=6a_{n-1}+7a_{n-2}an=6an−1+7an−2, find the least xxx such that an=O(xn).a_n = O(x^n).an=O(xn).
- We define Gabriel's Modified Horn as the shape generated when we revolve the graph of y=1xαy = \frac{1}{x^{\alpha}}y=xα1 around the xxx-axis for x≥1,x \geq 1,x≥1, where α>12\al…