0
$\begingroup$

I have seen the following definitions of little-o notation,

$(1)$ Let $f,g:\mathbb{R}\rightarrow \mathbb{R}$ . Then I say $f(x)=o(g(x))$ iff, $$\lim_{x\to\infty}\frac{f(x)}{g(x)}=0$$.

$(2)$ On the other hand I have also seen this definition on some websites, If $f(x)=o(g(x))$. Then there exists a $k\in\mathbb{N}$ such that $$f(x)\leq k g(x)$$ for all $x\geq x_{0}$ for some $x_{0}\in\mathbb{R}$

My question:-

I was just wondering how are they both equivalent. I am unable to get the intuition behind. How to understand this equivalence intuitively?

$\endgroup$
3
  • $\begingroup$ It's clear that these definitions are not equivalent. Take $f=g=1$ to see that (2) doesn't imply (1). $\endgroup$
    – David Kraemer
    Jul 12, 2022 at 19:49
  • $\begingroup$ I got the fault in my question as mentioned by @John White. $\endgroup$
    – RAHUL
    Jul 12, 2022 at 20:06
  • $\begingroup$ As an English sentence, the one you've written in (2) looks more like a theorem than a definition, the theorem being the true statement that $f\in o(g)\Rightarrow f\in O(g)$. $\endgroup$
    – Sassatelli Giulio
    Jul 13, 2022 at 6:56

1 Answer 1

Reset to default
6
$\begingroup$

The first definition is for little-o but the second one seems to be for big-O

$\endgroup$
4
  • $\begingroup$ Does little o have any meanings in terms of inequalities? $\endgroup$
    – RAHUL
    Jul 12, 2022 at 20:00
  • 2
    $\begingroup$ It should be $f(x) = o(g(x))$ if $\textbf{for every}$ $k \in \mathbb{R}^+$, there exists $x_0$ s.t. $f(x) \leq k g(x)$ $\endgroup$
    – John White
    Jul 12, 2022 at 20:03
  • $\begingroup$ @JohnWhite You mean $f(x)=O(g(x))$ $\endgroup$
    – PNT
    Jul 12, 2022 at 20:24
  • 2
    $\begingroup$ @PNT little o is same as big O where the constant can be any epsilon, that's why John wrote "for every k" (unheard, especially arbitrary small). $\endgroup$
    – zwim
    Jul 12, 2022 at 20:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .