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

Prove $\sum \limits_{i=1}^n i^2 \in \Theta (n^3)$

I'm preparing for an exam, and one of the review problems is to sort functions by order of growth, and this was the only summation in it. I know that $$\sum \limits_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6},$$ But what if I did not know the closed form?…
Caleb Jares
  • 603
4
votes
1 answer

How can I find a $k$ and a $n_0$?

Find $k$ such that $$(\lg n)^{\lg n}= \Theta (n^k), k \geq 2$$ That's what I did so far: $$(\lg n)^{\lg n}=\Theta(n^k) \text{ means that } \exists c_1,c_2>0 \text{ and } n_0 \geq 1 \text{ such that } \forall n \geq n_0: \\ c_1 n^k \leq (\lg…
evinda
  • 7,823
4
votes
0 answers

A general question of asymptotics

I am very desperately longing to know if there is a explicit relationship between $$F(n)=f(1)+f(2)+...+f(n)$$ and $$G(x)=\sum_{k=1}^{\infty}f(k)x^k$$ Assuming we can let $f$ be a sufficiently well behaved function, surely there must be a way of…
Elie Bergman
  • 3,917
4
votes
1 answer

Prove or disprove the Big-O of an exponential function

$f(n) = 2^{n+1} = O(2^n)$ Intuitively, I think the statement is false. However, when I go about disproving it, I find that $2^{n+1} = 2^n \cdot 2$, meaning that if there is a constant $C$ larger than $2$, then $|2^{n+1}| \le C|(2^n)|$, thus proving…
Ben
  • 41
4
votes
1 answer

Does this sum go to 0?

If we define $$ S = \sum_{k=1}^{\lceil n/2 \rceil} \binom n k \left(\frac{k}{n}\right)^{2k} \left(1 - \frac{k}{n}\right)^{2(n-k)} $$ Then when $n\to \infty$, does $S \to 0$?
NonalcoholicBeer
  • 7,211
4
votes
1 answer

Asymptotics of $\sum_{i=1}^n {n \choose i}2^i \frac{i+1}{i^{\frac{n + 1}{2}}}$

I have the following formula which appears numerically to be exactly $4n$ asymptotically. $$\sum_{i=1}^n {n \choose i}2^i \frac{i+1}{i^{\frac{n + 1}{2}}}$$ What can one do to prove this?
user35671
4
votes
3 answers

What is the order of the sum of log x?

Let $$f(n)=\sum_{x=1}^n\log(x)$$ What is $O(f(n))$? I know how to deal with sums of powers of $x$. But how to solve for a sum of logs?
Rob Hyndman
  • 219
4
votes
1 answer

Prove Linearity in Asymptotic Notation

The question: Prove O($\sum\limits_{k=1}^m(f_k(n))$) = $\sum\limits_{k=1}^m(O(f_k(n)))$ What I have done so far: Left side: Let g(n) = O($\sum\limits_{k=1}^m(f_k(n))$) For n > c, we have g(n) $\le$ C * ($f_1$(n) + $f_2$(n) + ... + $f_m$(n)) Right…
Matt
  • 41
4
votes
0 answers

Asymptotic solution involving the exponential integral.

I'm currently currently reading through a paper where the function $$R(t) = 1 -\sqrt{\dfrac{2t}{\beta}} - \dfrac{1}{\beta} \displaystyle{\left(\dfrac{2t}{3} + V\sum_{n=1}^\infty\left[\dfrac{2e^{-n^2\pi^2kt}}{n^2\pi^2} - \frac{\text{erf}(\pi…
Cornelius
  • 347
4
votes
1 answer

Logarithmic Asymptotic Solution

I'm currently reading through a paper where the relation $\dfrac{V}{1+V} = \dfrac{2}{\sqrt{\pi t}} \displaystyle{\sum_{n=0}^{\infty} \exp(-(2n+1)^2/4t)}$ (where $V$ is a constant value) is used to deduce the asymptotic equation: $\dfrac{1}{t} \sim…
Cornelius
  • 347
4
votes
2 answers

Is this the normal big-O?

My book on quantum mechanics introduces the notation $\mathcal O(1)$ as follows: We represent it by the formula $\Delta x \Delta k \gtrsim \mathcal O(1)$ where $\Delta x$ and $\Delta k$ are the "widths" of the two distributions, and we imply by…
user6701
4
votes
1 answer

Growth of $\Gamma(n,n)$

How can you get the asymptotics for the growth of $\Gamma(n,n)$? $$ \Gamma(n,n) = \int_n^\infty x^{n-1} \exp(-x) \mathrm{d}x $$
user66307
4
votes
2 answers

Finding asymptotes (horizontal / vertical) and obliques

Ok, well I would like to ask a few questions. Let's say we have a function $y=\displaystyle\frac{2 x^2}{x+2}$. So, the $D_f$ would be $\Bbb R \setminus\{-2\}$ right. To find the asymptotes, for vertical asymptote, do we search it if there is no…
user2041143
  • 309
4
votes
2 answers

Asymptotic behaviour of a sum of functions.

Suppose we have functions $f(x),g(x),u(x),v(x)$ such that $f(x)\sim g(x)$ and $u(x)\sim v(x)$ as $x\rightarrow x_0$. How can I show that $f(x)+u(x)\sim g(x)+v(x)$ as $x\rightarrow x_0$? I'm using the following definition: $$f(x)\sim g(x) \text{ as }…
user292256
  • 147
4
votes
1 answer

Comparing the growth of $f$ and $\bar{f} = \sum f$

(This question is in fact related to growth functions of groups) For two functions $f$ and $g$ (on the set of natural numbers) let us write $f\preceq g$ if there is $C\ge 1$ such that $f(n)\le g(Cn)$ for every $n\ge 1$. Let us write $f\sim g$ if…
user17488
  • 405
1 2 3
…
74 75