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

asymptotics of $\frac{c^{2(\log\log n)+1}-1}{c-1}$

Let $c>0$ be a constant and $n$ go to infinity. Asymptotically why is it the case that $\frac{c^{2(\log\log n)+1}-1}{c-1}\sim \log n^{2\log c}$ ? I don't think it changes anything but the actual relation is $$\frac{2c\log\log…
H. Walter
  • 979
  • 4
  • 9
1
vote
1 answer

Bernoulli trial and asymptotic analysis

I want to find such function $p(n)$ in a way that obtaining one succes will be asymptotically-equivalent to obtaining two failures. I basically want to have something like this: $$ \lim_{n \to \infty}{\frac{{n \choose 1}p(n)(1-p(n))^{n-1}}{{n…
Awerde
  • 299
1
vote
2 answers

Order of complexity proofs. Show that $n^3-5n+1=O(n^3)$.

Show that $n^3-5n+1=O(n^3)$. I did the following: Using the definition of big-Oh, we need to show that there exist $n_0$ and $C$ such that $n^3-5n+1 \leq Cn^3$ is valid for some constant $C > 0$ and for all $n > n_0$. First, choose $n_0=1$. Then…
Buddy
  • 21
1
vote
5 answers

Big Oh : How can i prove or disprove $8^{(n-3) }= O(2^n)$

How would I prove or disprove this? I tried it like this: $$8^{n-3}\in O\left(2^n\right)$$ $$8^{n-3}\leq c\cdot 2^n$$ $$8^n\cdot8^{-3}\leq c\cdot 2^n$$ $$8^n\leq c\cdot 2^n$$ (We can remove the $8^{-3}$ because it is a constant) But I'm really…
JangoCG
  • 139
1
vote
0 answers

Prove $f(n) = \omega(\log n) \implies n=O(2^{f(n)})$

Given that $f(n) = \omega(\log n)$ I need to prove that $n=O(2^{f(n)})$. I tried the following $f(n) = \omega(\log n) \implies \lim_{n \to \infty} \frac{\log n}{f(n)} = 0$ Then, I want to substitute $n=2^t \implies t=\log n$. Noting that when $n \to…
Eliran Turgeman
  • 183
1
vote
0 answers

$O(x^y)$ and $O(x^{y+1})$, $O(C^y)$ and $O(C^{y+1})$

Let $x$, $y$ be variables and $C$ be a constant. How do these $O$ notations compare? $O(x^y)$ vs $O(x^{y+1})$ (with $x^{y+1} = x * x^y$) and $O(C^y)$ vs $O(C^{y+1})$ (with $C^{y+1} = C * C^y)$ My first thought is the first two $(O(x^y)$ and…
Bob Mcjoe
  • 11
1
vote
1 answer

Watson's Lemma and Laplace transformation

Use Watson's lemma to find the expansion of $$F(\lambda) = \int_{0}^{\infty} e^{- \lambda t} sin(t)dt$$ ,and verfify the answer using Laplace transformation by expanding the answer using Taylor's expansion. Comparing the above integral with…
Atul Anurag Sharma
  • 652
1
vote
1 answer

asymptotic behavior of the solution to an ODE

Given $$y(t) = \frac{d_2 y_0 e^{d_2 t/\epsilon}}{d_2-\epsilon \, d_1 y_0 (e^{d_2 t/\epsilon}-1)}$$ I think that $y = O(1/\epsilon) $ as $\epsilon \to 0$. But as this is important for what I am doing and I am not used to asymptotic I wanted to…
chango
  • 2,060
1
vote
1 answer

Proof $(n^2 + 1)$ in $\Theta(n^3 - 2n - 3)$

I trying resolve this problem, but the first equation have 3 terms and the second equation have 2 terms. I don't know how to resolve this problem. Any idea?
sneyder05
  • 11
1
vote
0 answers

Big-Oh proof with (n+1)!

Prove that $T(n) = (n+1)! + 2^n$ is $O((n+1)!)$. Proof: by Big-Oh definition, $T(n)$ is $O((n+1)!)$ if $T(n) \leq c\cdot (n+1)!$ for some $n\geq n_0$. Let us check this condition. If $(n+1)! + 2^n \leq c\cdot(n+1)!$ then (this is the part I am…
erwoods89
  • 11
1
vote
1 answer

How to determine if f(n) = big theta(g(n))?

I have some issues in terms of the algebra I'm trying to solve for these 2 problems: Check if f(n) = Θ(g(n))? f (n) = 2log(n) vs. g(n) = n500 f (n) = (4 × n)150 + (2 × n + 500)400 and g(n) = 20 × n400 + (n + 500)200 So for the first function, I…
CD'A
  • 13
  • 3
1
vote
0 answers

Is the concept of time constant critical to only exponential functions?

From various applications in electrical and nuclear, I am convinced of the importance of 'time constant' when exponential expressions have to be dealt with. But I am curious to know if the time constant relates to only exponential decay (or rise) or…
Onkar Singh
  • 73
1
vote
2 answers

Asymptotic (big-O) complexity

I have the following problem: Order the following functions in increasing order of asymptotic (big-O) complexity. I'm not entirely sure how they got to the answer though. I seem to be getting a few correct in a row, but still overall unsure…
jjones5
  • 21
1
vote
1 answer

Show that the error terms in the asymptotic expansion of a binomial coefficient are uniformly bounded

I'm interested in the asymptotic behavior of $$ a_{n,k} :=\frac{1}{2^n} \binom{n}{\frac{n}{2} +k},$$ where $k$ is within a constant times $\sqrt{n}$, say $$ |k| < C \sqrt{n }.$$ Using Stirling's approximation, I found $$ a_{n,k} = \sqrt{\frac{2}{\pi…
Teddy
  • 2,396
1
vote
1 answer

Integral representation of a function

Here is another Prelim problem from Advanced Calculus. For $t>0$ and $D>0$ define $g(x,t)$ by $$ g(x,t)=\frac{1}{\sqrt{Dt}}\exp{\frac{-x^2}{4Dt}} $$ Now, for $f:\mathbf{R}\to\mathbf{R}$ being continuous with compact support, define $u(x,t)$ as…
Eager Student
  • 577
1 2 3
…
74 75