0

I have huge problems showing whether example like this:

enter image description here

is true or false using formal definition of Big O.

How can I solve such problems step by step?

I understand that formal definition of O(f(n)) is "for any n ≥ n0, f(n) ≤ cg(n)". What does it exactly mean though? I have no idea how to apply such to the example above. I am incredibly thick when it comes to this so I would really appreciate any resource hits or step by step explanation for true dummies. I do not need to have a specific answer, or explanation of steps on example I provided.

qwerty
  • 147

1 Answers1

2

Big-oh notation: $f(x)=O(g(x))$ means that $g(x)$ grows at the same rate, or faster, than $f(x)$. In other words, we can find a constant $C$ such that for $x$ sufficiently large, $f(x)\leq C\cdot g(x)$.

In your given example, to show that $$ 2+\log_2n=O\left(\frac{\log_2n}{2}\right), $$ you'll need to find a constant $C$ such that if $n$ is sufficiently large, $$ 2+\log_2n\leq C\cdot\frac{\log_2n}{2}. $$ To figure out what $C$ should be, we manipulate this last equation to get $$ 2\leq\left(\frac{C}{2}-1\right)\log_2n. $$ For this inequality to hold (since $n$ can get large), we don't want the coefficient of $\log_2n$ to be negative or zero. Therefore, let's try $C=4$ (because this gives nice numbers).

Therefore, we want the inequality $$ 2\leq\left(\frac{4}{2}-1\right)\log_2n=\log_2n. $$ Since this holds for all $n\geq 4$, we have a condition that for $n$ sufficiently large, $$2+\log_2n\leq 4\cdot\left(\frac{\log_2n}{2}\right).$$ This proves that $$ 2+\log_2n=O\left(\frac{\log_2n}{2}\right). $$

Michael Burr
  • 32,867