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
0
votes
1 answer

Some (Asymptotic) Bounds on Exponential Sums

Sorry if this is a duplicate, but can't find it anywhere. I'm learning some additive number theory and am stuck on showing some bounds. Let $S(\alpha, X) = \displaystyle \sum_{x=1}^{X} e(\alpha x)$ (where $e(\beta)$ just means $e^{2 \pi i…
Jon Hillery
  • 463
  • 2
  • 12
0
votes
1 answer

Determine the big $O$ notation

For $\epsilon>0$, why the following holds with $x$ larger enough $$O(x^{-\epsilon/2}\log x)=O(2^{-\log^{1/2}x})$$
Zoe
  • 155
0
votes
1 answer

How to prove f(n) is either O or Ω or Θ of g(n)?

Like the title says, I have that type of questions on an assignment. I checked the textbook and read many examples, but those examples are all very straight forward ones where the greatest order of the variable on both side are the same, but I am…
Jared Lee
  • 5
0
votes
0 answers

Do 'fundamentally hard' asymptotic problems exists?

I was watching Carl Bender's lecture 2 on YouTube and I stumbled across a 'fundamentally hard problem', namely the Schrodinger equation $y''(x)+Q(x)y=0$ (eq.1) Carl mentions that this is a 'fundamentally hard problem' because the most natural way…
Andy
  • 55
0
votes
3 answers

Asymptotic Analysis of $\log(1+x)$

I am trying to prove that $\log(1+x) \leq \sqrt{x}$ for all values $x>x_0$ which implies that $\log(1+x) = O(\sqrt{x})$. However, I am not able to get to this result. The result which states $\log(1+x) = O(x)$ is immediate as $\log(1+x) \leq x,…
Morteza Soltani
  • 193
0
votes
0 answers

Sum for asymptotics (asymptotic analysis)

Suppose $\mu>0$ $K>0$ $f(x)\sim -Ke^{-\mu x}$ as $x\to\infty$ $g(y)\sim -Ke^{-\mu y}$ as $y\to\infty$ x is always smaller or equal y, i.e. $x\leq y$ Does this imply that $$ f(x) + g(y) \sim -Ke^{-\mu x}-Ke^{-\mu y} $$ as $x\to\infty$ or…
Rhjg
  • 2,029
0
votes
1 answer

Usefulness of asymptotic (e.g., Big O) notation embedded in expressions

Recently I've been working through The Probabilistic Method by Alon and Spencer, and I've noticed that almost everywhere results (specifically bounds) are given using asymptotic notation. Here are some examples: On page 10 (Theorem 1.3.2), we bound…
kanso37
  • 358
0
votes
0 answers

Order of functions by rate of growth (from slowest to fastest) as $x$ gets very large

For the following functions, I ordered them from slowest to fastest as follows: 1st. $100^x$ 2nd. $5^x$ 3rd. $x^{100}$ 4th. $x^6$ 5th. $x^5$ 6th. $x^5\log_2x$ 7th. $\log_2x$ 8th. $5$ I got it wrong and received no feedback. Any clues? Thank you in…
Val
  • 41
0
votes
1 answer

Prove Big O notation with log

I need to prove $$ 2n^2+5n+20log(n)=O(n^2) $$ I know that the right needs change term to the greatest degree I got: $$ 2n^2+5n+20log(n)≤2n^2+5n^2+... $$ I want to how to deal with the log
Antonymous
  • 39
0
votes
1 answer

How can I determine the growth of this function?

In the complexity analysis of an algorithm, I encountered this function in $x$ for some small positive constants $a$, $b$ with $a>b>1$. $$f(x)={(a/b)^{\log_a(x(a-1)+1)}-1\over x(a/b-1)}$$ What is the asymptoptic growth of $f(x)$ as $x\to\infty$? …
FUZxxl
  • 9,307
0
votes
0 answers

exponential function of of big O

Can someone please help me solve the following? $$f=exp\{\frac{P(x)}{Q(x)}\} = exp\{\frac{a+x+O(x^2)}{b+x+O(x^2)}\} = exp\{\frac{a+x}{b+x}+O(x^2)\}=exp\{\frac{a+x}{b+x}\}+O(?)$$ For the nominator $O(x^2) $ as $n\rightarrow0$ For the denominator…
LLT
  • 5
0
votes
1 answer

Asymptotic/Big-O notation with multiple variables?

I'm a little confused with the following problem. Given two $n$-bit positive numbers $a; b$, compute $a^b$. How many bits does it take to write down the answer, in the asymptotic notation? I've worked out that the general way to express the number…
John
  • 1
  • 2
0
votes
0 answers

Altering the curvature of an asymptotic curve?

With a basic function like $y = 1/x$ mapped over the first 100 integers I see the curve elbow at around 5. I want to shift this closer to 100... to "flatten" the curve so to speak, so it grows more quickly on the right of the elbow and less so on…
ekkis
  • 101
  • 2
0
votes
1 answer

Asymptotic order of arithmetic functions

If $f,g:\mathbb{N}\rightarrow\mathbb{R}$ are two functions such that $f(n)=O(g(n))$, then what can we say about the order of $\prod_{i=1}^nf(i)$ in terms of $g(\cdot)$? Any suggestion is welcome.
QED
  • 12,644
0
votes
1 answer

Prove that $3^{2^n}=o(2^{3^n})$

I'm not sure if this method is valid so I'd like some feedback. $$L=\lim_{n\to\infty}\frac{3^{2^n}}{2^{3^n}}=\frac{\infty}{\infty}=\lim_{n\to\infty}\frac{\frac{\mathrm d}{\mathrm dn}(3^{2^n})}{\frac{\mathrm d}{\mathrm…
Revoltechs
  • 321
  • 1
  • 9
1 2 3
…
74 75