Skip to main content

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

Back to Algorithms

An original ProofAnvil practice problem, written for this course. ProofAnvil is a practice course, not a homework-answer service.