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

Examples of sub-exponential functions that aren't exponential functions when chained by a polynomial

Wikipedia talks about two groups of functions with asymptotic growth rates between polynomial and exponential – quasi-polynomial functions and sub-exponential functions. It only gives two examples of such a function, however, and those functions are…
Joe Z.
  • 6,719
8
votes
2 answers

Big oh of $(n+1)\sqrt{n-1}$

My instructor claims this is $O(n)$, but shouldn't it be $O(n^{1.5})$? If we ignore the $+1$ and $-1$ then this is just $O(n^{1.5})$. Is this reasoning right? Any help is appreciated.
XKCD
  • 141
8
votes
1 answer

What is $Θ(f(n)) - Θ(f(n))$?

$$\Theta(f(n)) - \Theta(f(n)) =\; ?$$ I find this exercise from my algorithm analysis book very confusing because it's subtracting 2 function sets. Any hints/answers are welcome. Thanks!
Mihai Neacsu
  • 305
8
votes
3 answers

Is it legitimate to write nested big-Os in an asymptotic formula for a multivariable function?

Suppose I have a 2-variable function $g(k,n)$ and I know that $g(k,n)=O(n^{f(k)})$, for fixed $k$ as $n \rightarrow \infty$, for some function $f=f(k)$. Suppose I also know that $f(k)=O(\log k)$. Is it legitimate to write $g(k,n)=O(n^{O(\log…
Douglas S. Stones
  • 21,079
7
votes
2 answers

Prove or disapprove the statement: $f(n)=\Theta(f(\frac{n}{2}))$

Prove or disapprove the statement: $$f(n)=\Theta(f(\frac{n}{2}))$$ where $f$ is an asymptotically positive function. I have thought the following: Let $f(n)=\Theta(f(\frac{n}{2}))$.Then $\exists c_1,c_2>0 \text{ and } n_0 \geq 1 \text{ such that }…
evinda
  • 7,823
7
votes
2 answers

What operations is this asymptotic relation closed under?

For all positive functions $f$ and $g$ of the real variable $x$, let $\sim$ be a relation defined by $f \sim g$ if and only if $\lim_{x \rightarrow \infty} \frac{f(x)}{g(x)} = 1$ Then if $f \sim g$, we have for example, that $f^2 \sim g^2, \sqrt{f}…
user912803
  • 71
7
votes
1 answer

Proving $n \log n \in O(n^{1+\epsilon})$ without limits

How can one show that $n \log n \in O(n^{1+\epsilon})$ where $0 < \epsilon < 1$ without using limits? This question arise from a homework where I used limits to prove the relation. I'd like to know if there is another way.
Li-thi
  • 269
7
votes
3 answers

Why is $\sum_{k = n}^{\infty} (\log k)^2/k^2 = O \left((\log n)^2/n \right)$?

The question comes from a statement in Concrete Mathematics by Graham, Knuth, and Patashnik on page 465. $$\sum_{k \geq n} \frac{(\log k)^2}{k^2} = O \left(\frac{(\log n)^2}{n} \right).$$ How is this calculated?
Antonio Vargas
  • 24,993
7
votes
1 answer

The sum $\sum\limits_{n \ge 0} \binom{m-1}{n} \frac{n!}{m^n} + \binom{n+1}{2}\binom{m-1}{n-1}\frac{(n-1)!}{m^n}$ is asymptotic to $\sqrt{9πm/8}$

Consider the following sum, known as Ramanujan's Q-function: $$\begin{align} Q(m) &= 1 + \frac{m-1}{m} + \frac{(m-1)(m-2)}{m^2} + \cdots + \frac{(m-1)(m-2) \cdots 1}{m^{m-1}} \\ &= \sum_{n \ge 0} \binom{m-1}{n}\frac{n!}{m^n} = \sum_{n \ge 0}…
ShreevatsaR
  • 41,374
7
votes
1 answer

Substituting big-$O$ and reaching a final expression.

I usually don't like to ask questions that are too specific, but I cannot reach the exact final expression. Lemma A function $f: \mathbb{N} \to \mathbb{C}$ verifies $$|f(n)| \leq \frac{\log{|g(n)|}+\frac{1}{2}\log{\left(\tfrac{h(n) \varepsilon}{4…
Macarena Perelman
  • 73
7
votes
4 answers

Big $\mathcal{O}$ Notation question while estimating $\sum \frac{\log n}{n}$

I have a function $S(x)$ which is bounded above and below as follows: $f(x) + C_1 + \mathcal{O}(g(x)) < S(x) < f(x) + C_2 + \mathcal{O}(g(x))$ as $x \rightarrow \infty$ Can I conclude that $$S(x) = f(x) + C + \mathcal{O}(g(x))$$ as $x \rightarrow…
user17762
6
votes
1 answer

The Asymptotic Expansion of The Exponential Integral

I was reading R. Wong's book on Asymptotic Approximations of Integrals, and I'm having problems with the derivation of the asymptotic expansion of the exponential integral which he defined as follows: $$ Ei(z)=\int_{-\infty}^z \frac{e^t}{t} dt,…
Kurome
  • 1,121
6
votes
3 answers

How to show $\sum\limits_{i=1}^n\log\left(\frac{n}i\right)= \Theta(n)$?

Is the sum from i=1 to n for log(n/i) = Θ(n)? Im studying for a test and appreciate your help. This is what I did: and got something else $$\sum_{i=1}^n \log(n/i)=\sum_{i=1}^n[\log n-\log i]=\left(\sum_{i=1}^n\log n\right)-\left(\sum_{i=1}^n \log…
Mary
  • 825
6
votes
1 answer

Is there a function $h$ and a constant $c$ to satisfy $h(x-c) \neq O(h(x))$

Is there a function $h$ and a constant $c$ to satisfy $h(x-c) \neq O(h(x))$? My attempt: This claim isn't true. we shall show an equivalent claim to the negation of our claim. We will show that for each function $h(x)$ and a constant $c$, from a…
Chopin
  • 872
6
votes
2 answers

Prove $\log x!$ is $\Omega (xlogx)$

Find a positive real number $C$ and a nonnegative real number $x_o$ such that $Cx$$\log x$ $\leq$ $\log x!$ for all real numbers $x > x_o$. I tried to expand $\log x!$ into $\log 1 + \log2 +\log3 +....\log x$. But how do I choose $C$ and $x_o$ so…
user59036
  • 1,525
1
2
3
…
74 75