Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [asymptotics]

For questions involving asymptotic analysis, including function growth, Big-$O$, Big-$\Omega$ and Big-$\Theta$ notations.

Questions involving asymptotic analysis, including function growth, Big-$O$, Big-$\Omega$ and Big-$\Theta$ notations.

  • $f(x) = O(g(x))$ as $x \to \infty$ is used to mean that for sufficiently large values of $x$, we have $|f(x)| \leq A g(x)$ for some constant $A$.

  • $f(x)=\Omega(g(x))$ is equivalent to saying that $g(x)=O(f(x))$.

  • $f(x)=\Theta(g(x))$ is used to mean that $f(x)=O(g(x))$ and that $f(x)=\Omega(g(x))$.

9469 questions
1
vote
1 answer

How to prove that o(f(n)) is in O(f(n))?

I tried to prove that "$o(f(n)) \in O(f(n))$". I knew intuitively that the proposition is true, through the fact that $n^2=O(n^k), \forall k \ge 2$, but $n^2\ne o(n^k), \forall k>2$. However, I want to prove this mathematically. My proof: $o(g(n))…
Danny_Kim
  • 3,423
1
vote
1 answer

Can someone check my process of proving "if lim(f/g)=0, then f(n)=o(g(n))"?

I am trying to prove the following statement. if $\displaystyle \lim_{n\rightarrow\infty}\frac{f(n)}{g(n)}=0$, then $f(n)$ is $o(g(n))$ My solution $o\left(g(n)\right)=\{f(n):\forall c>0, \exists n_0, \forall n>n_0, 0 \le f(n) \lt cg(n)\}$ $0 \le…
Danny_Kim
  • 3,423
1
vote
1 answer

Asymptotic ordering of functions

Suppose we define a relation on functions $\mathbb{R}_{\geq 0}\rightarrow\mathbb{R}_{\geq 0}$ as follows: $f<
user270861
  • 13
1
vote
3 answers

$O( n^3)$ vs $O(n^2 \ log n)$

I was wondering how $n^3$ compares to $2n^2 \log n$ as I thought that $n^3$ is $\Omega(n^2 \log n)$ but there is the fact that $n$ is $O(n \log n)$ so I wasn't sure whether it is bigO or $\Omega$
jn025
  • 989
1
vote
1 answer

Product property of Big O

Trying to prove: If $f(n)$ and $g(n)$ are both $O(h(n))$, then $f(n)*g(n)$ is $O(h^2(n))$. Understanding so far : The product of upper bounds of functions gives an upper bound for the product of the functions: proof: If $g_1(n) \le c_1\…
Ka Mal
  • 53
1
vote
0 answers

Asymptotic form of Whittaker function

I am working with Whittaker functions for a project and have no experience with asymptotic analysis - how is the following expression, for $\kappa \rightarrow \infty$ through the real numbers …
Schwinger
  • 329
1
vote
0 answers

Compare growth of function and derivative

Suppose $f:\mathbb R \rightarrow \mathbb R$, $O(1)
Jong
  • 236
1
vote
1 answer

Compare growth of function and its derivative.

Suppose $f:\mathbb R \rightarrow \mathbb R$, $f(x)\delta$, $x f'(x) < f(x)$ for all functions…
Jong
  • 236
1
vote
2 answers

Can $O(\sqrt{x})$ be considered $o(x)$?

This example challenges my understanding of $O(x)$ and $o(x)$ notation. One the one hand I have: $$ A = B + o(x)$$ Another part of the paper uses big-O instead of little-o and says: $$ C = D + O(\sqrt{x}) \stackrel{?}{=} D + o(x)$$ I am willing to…
cactus314
  • 24,438
1
vote
1 answer

Comparing Serveral Asymptotic Analysis Question

I have the following: $n^2\log(n)$, $2^n$, $2^{2^n}$, $n^{\log(n)}$, $n^2$. In increasing order, I think their order of growth is $n^{\log(n)}$ < $n^2$ < $n^2\log(n)$ < $2^n$ < $2^{2^n}$ because I take log of all of them and found this…
RexYuan
  • 140
1
vote
1 answer

How to solve this type of exercises $\sqrt{x^6+x^5-2x^3+O(x^2)}$

I have a simulation test with this type of exercise, asymptotic expansion: $$\sqrt{x^6+x^5-2x^3+O(x^2)}$$ with $$ x\rightarrow \infty$$ I have studied the theory of Landau's symbols but I have no idea about how to solve. Can someone please explain…
Christian Giupponi
  • 687
1
vote
1 answer

How can I prove $n - 2\sqrt{n} = \Theta(n)$

I want to prove the following $$n - 2\sqrt{n} = \Theta(n)$$ It's $n - 2\sqrt{n} \leq n = O(n)$ How can I prove the same for $\Omega(n)$
user248445
  • 53
1
vote
2 answers

How can I show that $\sum \limits_{i=1}^n i^2$ is $O (n^3)$

I am preparing for an exam, and one of the problems on the study guide is: Show that $\sum \limits_{i=1}^n i^2$ is $O (n^3)$ If we declare n as some arbitrary number 5, then our summation would read $1^2$ + $2^2$ + $3^2$ + $4^2$ + $5^2$ Everything…
User
  • 907
1
vote
1 answer

Order estimates

QUESTION: Suppose $y(x) = 3 + O (2x)$ and $g(x) = \cos(x) + O (x^3)$ for $x << 1$. Then, for $x << 1:$ (a) $y(x)g(x) = 3 + O (x^2)$ (b)$ y(x)g(x) = 3 + O (x^4)$ (c) $y(x)g(x) = 3 + O (x^6)$ (d) None of these MY WORKINGS: $y(x) = 3+O(2x) = 3 + O(x)…
Dr.Doofus
  • 245
1 2 3
…
74 75