Algorithms · Correctness proofs and asymptotic complexity
Let all logarithms have base 2, and let all functions have domain the positive integers
Problem
Let all logarithms have base \(2\), and let all functions have domain the positive integers. For each pair \(f,g\) below, determine which of the relations \(f\in O(g)\), \(f\in\Omega(g)\), \(f\in\Theta(g)\), \(f\in o(g)\), and \(f\in\omega(g)\) hold. Prove every conclusion directly from the definitions of the five asymptotic relations. 1. \(f(n)=7n^2+3n+4\) and \(g(n)=n^2\). 2. \(f(n)=n^{3/2}\log n\) and \(g(n)=n^{3/2+1/100}\). 3. \(f(n)=2^{\sqrt{\log n}}\) and \(g(n)=(\log n)^{10}\). 4. \(f(n)=n\) for even \(n\) and \(f(n)=2n\) for odd \(n\), while \(g(n)=n\).
Hint
** Study \(f(n)/g(n)\), but translate each limit conclusion back into an eventual quantified inequality.
Check your work
Work the problem yourself first. Then open it in Training to check your answer and read the full worked solution.
Create a free account to check your answer and see the solution. Create a free account.
More Algorithms practice problems
- There are n jobs in fixed order with positive integer sizes s_1,…,s_n, and d≥1…Correctness proofs and asymptotic complexity
- Two disjoint color classes contain r≥1 red and b≥1 blue planar pointsDivide-and-conquer algorithms
- Using only comparisons, return both minimum and maximum among n≥1 distinct keysDivide-and-conquer algorithms
- Consider the invalid coding rule that repeatedly combines the two partial trees of…Greedy algorithms and exchange proofs
- The n vertices of a cycle are numbered 1,…,n, and vertex i has an integer weightGreedy algorithms and exchange proofs
- Given an undirected graph with up to five million vertices, produce exactly the…Dynamic programming and state design
- Prim’s algorithm starts at an arbitrary root and repeatedly adds a minimum-weight edge…Dynamic programming and state design
- Let T[0..n-1] be a text and P[0..m-1] a pattern over the same alphabet, where 1≤ m≤ nGraph optimization and traversal algorithms
- Consider SET COVER parameterized by the universe size p=|U|, while the number m of…Reductions, NP-completeness, and approximation