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
0 answers

WKB leading order

I'm learning about the WKB method, and I'm applying it to an assignment. The assignment question asks to find the "leading order" WKB expansion for the particular equation. For WKB you make the substitution: $$y \sim \exp…
Bamboo
  • 1,049
1
vote
1 answer

Why is $1 - \cos(x)$ of $\mathcal{O}(x^2)$?

I know the definition of order estimates, For the solution to apply we need to show: $ \displaystyle\lim_{x \to 0} \frac{1 - \cos(x)}{x^2} = A \neq 0\space or \space \infty$ But how can one show this?
jugugularstrik
  • 11
1
vote
3 answers

Upperbound confusion

Why is the following true? $3n^2-100n+6$ is big $O$ of $n^2$ This has been demonstrated to be true when $c$ is $4$ and $n$ is $10$. $3*100-1000+6 = -694 = 694$ is the absolute value is a big $O$ of $4*100 = 400$ It looks like $n^2$ is a lot less.…
user235991
  • 57
1
vote
1 answer

Interpreting little-$o$ notation

This is the integrand of a complex integral: $$\frac{o(\zeta - z)}{\zeta - z}$$ The ensuing discussion says that this can be made as small as desired [by confining $\zeta$ close to $z$]. In general I thought little-$o$ notation implied that given…
user12802
1
vote
1 answer

Asymptotic expansion for the inverse of a matrix-valued function

suppose I have an asymptotic expansion for a matrix-valued function $\psi : \mathbb{C} \to \mathbb{C}^{2 \times 2}$ : $$\psi(\lambda) \sim I + \frac{m_1}{\lambda} + \frac{m_2}{\lambda^2} + \cdots \ \ \ \ \lambda \to \infty$$ where $m_i$ are…
the8thone
  • 4,111
1
vote
3 answers

Comparing growth rate of $n^{\log_2{5}}$ vs $n^2 \log{n}$

$\log_2{5}$ is 2.3219.. and thus $n^{\log_2{5}} = n^{2.3219}$. Comparing that with $n^2 \log{n}$ which already has an $n^2$ in front, which one grows faster? I notice that $n\log{n}$ is between $n$ and $n^2$. But I don't know how log compares in…
maregor
  • 235
1
vote
0 answers

Asymptotic Proof

Can someone explain this asymptotic proof to me.I am stuck at the inductive step and get lost around this step $2 × n! < (n + 1) × n!$ $$2n = o(n!)$$ True Proof: In order to $2n = o(n!)$ be true, there should exist $n_0$ and a constant c such that…
user4203815
  • 95
1
vote
3 answers

Big-O notation examples

How do I get c = 4 and n0 = 21, I understand that I could plug in different numbers till f(n) ≤ c * n for all n ≥ n0, but using f(n) how do I arrive at those numbers? 3n^3 + 20n^2 + 5 3n^3 + 20n^2 + 5 is O(n^3) need c > 0 and n0 ≥ 1 such that 3n^3 +…
JTK
  • 137
1
vote
1 answer

Suppose that $f (x) =O(g(x))$. Does it follow that $\log |f (x)| =O(log |g(x)|)$?

Suppose that $f(x)=O(g(x))$. Does it follow that $\log |f (x)|=O(log |g(x)|)$? I start from $f(x)=O(g(x))$, until I get Does it mean $\log |f (x)|=O(log |g(x)|)$?
james brown
  • 460
1
vote
1 answer

Big-theta notation

I was wondering about big-theta ($\Theta$) notation. A) Is $\Theta(n/2) \leq \Theta(n)$ for $n$ being an integer? I know that $n/2 = O(n)$, but does it also mean that $\Theta(n/2) \leq \Theta(n)$? B) If I add two theta terms, so let's assume, we…
Johnny Bravo
  • 11
1
vote
1 answer

Is Θ(⌈x/4⌉) = Θ(x)?

I'm currently working on aysmptotic notation. I know the basic laws of big theta, O, and omega. But I'm having a little confunsion in understanding simplifying the expressions (if that's even possible). I'm essentially wondering if the following is…
Wolff
  • 573
1
vote
2 answers

Big $O$ -- $3^n$ vs $n\cdot2^n$

I'm trying to compare $f(n) = 3^n$ and $g(n) = n\cdot2^n$ to determine whether $f \in O(g)$, $f \in \Omega(g)$, or $f \in \Theta(g)$. My gut is telling me that $g(n) = n\cdot2^n$ grows faster, and so $f \in O(g)$, but I'm having a hard time coming…
Ryan
  • 311
1
vote
1 answer

Proof $(\log(n))^{\log(\log(n))} = O(n)$

Can someone provide a proof that $(\log(n))^{\log(\log(n))} = O(n)$? Preferably without calculus, but I'll take what I can get. Just ran into this problem, and I have no way of moving forward, especially considering $\log(n)^{\log(n)} \not= O(n)$.
user82004
1
vote
2 answers

Is $\lceil{\lg n}\rceil!$ polynomially bounded?

Is $\lceil{\lg n}\rceil!$ polynomially bounded? I've tried using Stirlings Approximation, and I get that $\lceil{\lg n}\rceil! \approx \sqrt{2\pi}\lceil{\lg n}\rceil^{1/2}\lceil{\lg n}\rceil^{\lceil \lg{n} \rceil}e^{-\lceil \lg{n} \rceil}$ But I'm…
MathStudent
  • 1,352
  • 11
  • 22
1
vote
0 answers

Calculating Upper bound of a function

If T(N) = T(sqrt(N)) + 1 and T(1) = 1 then what is the upper bound i.e O(N) for this function? sqrt(N) => square root of N
user1918858
  • 131
1 2 3
…
74 75