Chapter 2, Problem 4E

Program Plan Intro

Big O definition:

The Big O definitions for “f₁(n)” and “f₂(n)” are shown below:

• The function “f₁(n)” is O(g₁(n) if positive numbers “c₁” and “N₁” exists such that $f_1\left(n\right)\le c_1{g}_1\left(n\right)$ for all $n\ge N_1$.
• The function “f₂(n)” is O(g₂(n) if positive numbers “c₂” and “N₂” exists such that $f_2\left(n\right)\le c_2{g}_2\left(n\right)$ for all $n\ge N_2$.

Explanation of Solution

(b) $f_1\left(n\right)/f_2\left(n\right)isnotO\left(g_1\left(n\right)/g_2\left(n\right)\right)$

• Take $f_1\left(n\right)=a_{1}n$ and $f_2\left(n\right)=a_{2}n$