Question

For each of the following pairs of functions, determine whether 𝒇(𝒏) = 𝑶(𝒈(𝒏)) or

𝒈(𝒏) = 𝑶(𝒇(𝒏)).

a. 𝑓(𝑛) = 𝑛(𝑛 − 1)⁄2 and 𝑔(𝑛) = 6𝑛

b. 𝑓(𝑛) = 𝑛 + 2√𝑛 and 𝑔(𝑛) = 𝑛^2

c. 𝑓(𝑛) = 𝑛 + log 𝑛 and 𝑔(𝑛) = 𝑛√𝑛

d. 𝑓(𝑛) = 𝑛 log 𝑛 and 𝑔(𝑛) = 𝑛√𝑛/2

e. 𝑓(𝑛) = 2(log 𝑛)^2

and 𝑔(𝑛) = log 𝑛 + 1

Answer 1

a.

$g(n)=6n\le 6f(n)=6n(n-1)$

𝒈(𝒏) = 𝑶(𝒇(𝒏))

b.

$𝑓(𝑛) = 𝑛 + 2\sqrt𝑛\le 3n\le 3𝑔(𝑛) = 3𝑛^2$

𝒇(𝒏) = 𝑶(𝒈(𝒏))

c.

$𝑓(𝑛) = 𝑛 + log 𝑛\le 2n\le 2𝑔(𝑛) = 2𝑛\sqrt 𝑛$

𝒇(𝒏) = 𝑶(𝒈(𝒏))

e.

$𝑔(𝑛) = log 𝑛 + 1\le 2logn\le 2f(n)=2(log 𝑛)^2$

𝒈(𝒏) = 𝑶(𝒇(𝒏))

d.

$𝑓(𝑛) = 𝑛 log 𝑛\le n\sqrt n=2𝑔(𝑛)$

𝒇(𝒏) = 𝑶(𝒈(𝒏))