1
$\begingroup$

I'm studying for the NSW HSC Extension 2 exam, and i'm wondering whether using Big O Notation is an appropriate approach to the question below. I'm asking because it doesn't seem rigorous or even correct, yet as far as my understanding of asymptoic analysis goes, it's sound. These exams don't require rigorous or formal proofs. Even though Big O and Big Θ aren't covered, the phrasing "or Otherwise" allows one to use results from beyond the curriculum. In limit questions they accept L'hopitals rule, for instance. To make it acceptable, would I have to actually include the reasoning that $O(x^2) > O(x)$ ? (NSW HSC EXT2 2010 Q7 b)

The graphs of $ y = 3x - 1 $ and $ y = 2^x $ intersect at (1,2) and (3,8). Using these graphs, or otherwise, show that $ 2^x \ge 3x - 1 $ for $ x \ge 3 $

$$O(2^x) = O(a^x) for a > 1 $$ $$O(3x - 1) = O(x)$$ $$O(a^x) > O(x) for a > 1$$ $$2^x = 3x - 1 at x = 3 $$ therefore $ 2^x \ge 3x - 1 $ for $ x \ge 3 $

The markers guide to answering is either in graphing the functions and inspecting. Would say, taking the limit $frac{(2^x)}{3x - 1}$ for x approaches infinity, and showing this is infinite be better? I ask as i'm averse to the temporal cost of graphing.

$\endgroup$
5
  • $\begingroup$ First of all you have to say if you are doing some asymptotic comparison as $x \to +\infty$ or $x \to 0$ or something else. For example $x = \mathcal{O}(x^2)$ as $x \to +\infty$ but not as $x \to 0$. And $\mathcal{O}(f(x)) > g(x)$ doesn't mean anything, go back to the definition of $f(x) = \mathcal{O}(g(x))$ $\endgroup$
    – reuns
    Commented Oct 5, 2016 at 9:11
  • $\begingroup$ Though if $O(f(x)) = cg(x)$ for $x > x_0$, then should I say $f(x) = cg(x)$, $c . 1$ for $x > x_0$? Is that a valid way to express what i'm trying to say? $\endgroup$
    – Brayton
    Commented Feb 6, 2017 at 11:09
  • $\begingroup$ e.g. Since $x > log(x)$ for sufficiently large $x$, can I say $O(x) = O(log(x))$ while $O(log(x)) /neq O(x)$ $\endgroup$
    – Brayton
    Commented Feb 6, 2017 at 11:12
  • 1
    $\begingroup$ No, the big O-notation bounds the LHS by the RHS ! So go back to the definition : $f(x) = O(g(x))$ as $x \to +\infty$ if and only if there are some constants $a,c$ such that $\forall x > a, |f(x)| < c |g(x)|$ $\endgroup$
    – reuns
    Commented Feb 6, 2017 at 11:26
  • 1
    $\begingroup$ From this, it is acceptable to write that as $x \to +\infty$, $\log(x) = O(x) = O(e^x)$, but not that $O(e^x) = O(x)$ $\endgroup$
    – reuns
    Commented Feb 6, 2017 at 11:27

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .