-1

For time complexity I get that:

  • O(n) = worst case

  • $\Omega$(n) = best case

  • $\Theta$(n) = exactly (best and worse)

But I'm facing the following:

"State weather the statement is true or false. If true, provide justification, and if false, give the correct relation."

  1. $f(n) = log\ n, g(n) = \sqrt n\ $and $ f = O(g)$
  2. $f(n) = 2^n$, $g(n) = 4^n$, and $f = \Omega(g)$
  3. $f(n) = n^3 - n^2$, $g(n) = n^2$, and $f = O(g)$
  4. $f(n) = 2n + log\ n$, $g(n) = 2n\ log\ n$, and $f = \Theta(g)$
  5. $f(n) = log_2\ n$, $g(n) = log_{10}\ n$, and $f = \Theta(g)$

Is this anything more complicated than plugging in values for n to see which one grows faster?

E.g.

  1. True. E.g. if $n = 256$, both $log_2$ and $log_{10}$ of 256 (8, 2.4) are $ < 16$,
  2. False. $f = O(g)$ because $g(n) > f(n)$ for all positive values of $n$.
  3. False. $f = \Omega(g)$ At large values of $n, n^3$ will dwarf $n^2$.
  4. False $f = O(g)$ since $2n + log\ n$ is much smaller than $2n log\ n$.
  5. True. Regardless of the log base they will both grow at the same rate.

Am I doing this right? Or am I missing something?

OrdinaryHuman
  • 219
  • Plugging in test-values will not tell you for certain what will happen for ALL values of the functions as $n\to\infty.$ For Q.1 we have $(\log n)/n\to 0$ as $n\to \infty$ so for any constant $k>0$ we have $(\log n)/n^k=$ $(1/k)\cdot (\log (n^k))/n^k$ $\to 0 $ as $n\to \infty.$ – DanielWainfleet Mar 20 '17 at 10:00
  • OK, so the process is what? Solve for the limit of n as n goes to infinity? – OrdinaryHuman Mar 20 '17 at 15:45

2 Answers2

1

Definition of Big O is not that simple as (worst case) even when this is the purpose of this notation. To prove some function f is O(g) you need to prove that exist some value $x_0 > 0$ and $M > 0$ such that $\forall x > x_0$ $| f(x)| < M *| g(x) |$

Check the formal definition on wikipedia

Marcelo Fornet
  • 315
  • Wikipedia only states the form of the definition you just repeated, it does nothing to help me solve the 5 items above. – OrdinaryHuman Mar 20 '17 at 15:44
-1

Apparently the way to answer these is the following 3 identities:

$f = O(g)$ if $\lim_{n \to \infty} \frac{f}{g} < \infty$

$f = \theta(g)$ if $\lim_{n \to \infty} \frac{f}{g} = 0$

$f = \Omega(g)$ if $\lim_{n \to \infty} \frac{f}{g} > 0$

Less formally:

  • if $f$ grows slower than $g$, then $\Omega(g)$
  • if $g$ grows faster than $f$, then $O(g)$
  • if $f$ and $g$ grow at the same rate, then $\Theta(g)$

Back to the five:

(a):

$lim_{n \to \infty} (\frac{log\ n}{\sqrt n})$

True. $f$ will always grow slower than $g$, so $f = O(g)$.

(b):

$\frac{2^n}{4^n}$ can be rewritten as $(\frac{2}{4})^n$, which is $(\frac{1}{2})^n$, which clearly heads toward $0$ as $n$ goes to $\infty$, so this is false, $f != \Omega(g)$, $f = O(g)$.

(c):

$\frac{n^3-n^2}{n^2}$ Factor out the $n^2$ and cancel and you get $n-1$. That shows $f$ grows faster than $g$ hence (c) is false, $f != O(g)$, instead $f = \Omega(g)$.

(d):

$\frac{2n+log\ n}{2n\ log\ n}$ $f$ will always grow slower than $g$, hence this is false, $f = O(g)$ not $\Theta(g)$.

(e):

$\frac{log_2\ n}{log_{10}\ n}$ While $log_{10}$ is 'bigger' than $log_2$ they grow at the exact same rate hence this is true, $f = \Theta(g)$.

In other words, I had the right idea, but just plugging in big values isn't a legitimate way to justify the answer since functions can vary at different values of n.

Ideally you could use fancier algebra to reduce these expressions but the general idea for those of us who don't need mathematical formalism to function (no pun intended) it's a matter of identifying which grows faster, then justifying it.

OrdinaryHuman
  • 219
  • 1
    These exercises are there to teach you/let you practice the formal way to do it, so that when you get harder "real-life" examples which you cannot solve just by intuition, you have a method in your toolbox to solve the problem. You can say you don't need to practice, but that's not going to get you through the course. (And you still haven't properly solved d and e.) – TMM Apr 07 '17 at 05:55
  • 2
    Your interpretations of $O$, $\Theta$, and $\Omega$ at the top are incorrect. They should be $$\begin{align} &f = O(g) \quad \text{if} \quad \lim f/g \in [0,\infty), \ &f = \Theta(g) \quad \text{if} \quad \lim f/g \in (0,\infty), \ &f = \Omega(g) \quad \text{if} \quad \lim f/g \in (0,\infty]. \end{align}$$ – Antonio Vargas Apr 07 '17 at 16:45
  • @AntonioVargas, The point of this question was to seek an algorithm to respond to the prompts, not provide a detailed, rigorous formalism on the exact definition of the limit of $\Omega$, $\Theta$, $O$. This kind of response isn't spectacularly helpful, as someone who can deduce the correctness of the prompts probably already knows what you just said, and someone who doesn't isn't going to be elucidated by it. – OrdinaryHuman Apr 08 '17 at 19:34
  • It's also classic Stack Overflow -- no one attempts to provide a helpful answer, but many rush to criticize your attempt and downvote both your questions and answers. And people wonder why less than 8% of the 4 mil users post more than 1 question. – OrdinaryHuman Apr 08 '17 at 19:37
  • If you didn't understand my comment you could have just said that and I would have clarified. – Antonio Vargas Apr 08 '17 at 20:03