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

Formally prove/disprove that $\sqrt{n}o(\sqrt{n}) = o(n)$

I'm wondering how to formally show that $\sqrt{n}o(\sqrt{n}) = o(n)$. The problem I'm having is that I don't really know how to formally resolve the multiplication on the LHS. It would be straightforward to show the result for $\sqrt{n}O(\sqrt{n}) =…
somebody
  • 1,085
  • 4
  • 11
  • 19
1
vote
1 answer

Prove that if $\log{f(n)} \in O(g(n))$ then $f(n)\in O(3^{g(n)})$

Let $\mathcal{F}=\{f|f:\mathbb{N}\to\mathbb{R}^+\}$ $$\forall f\in\mathcal{F}: \log{f(n)} \in O(g(n))\implies f(n)\in O(3^{g(n)}).$$ How to prove this? I thought about first showing that $$g(n) \in O(3^{g(n)})$$ Then $$\log{f(n)} \in O(f(n))$$…
Amir Mousavi
  • 171
1
vote
1 answer

Minimizers of an expression with little O notation

Suppose that $f(x) = o(\sqrt{x})$ as $x\rightarrow\infty$ and let $x^*(a)$ denote the minimizer of $f(x) + a^{3/2}/x$, that is, the value of $x$ that minimizes said expression (assuming such a value exists). As $a\rightarrow\infty$, is it true that…
Charlie
  • 13
1
vote
1 answer

Asymptotic relations at infinity

I am attempting to show that If $f(x) - g(x) \ll 1,\, x \to \infty$, then $e^{f(x)}\sim e^{g(x)}, \,x\to \infty$ From the first line, I am able to show that $$ \lim_{x\to \infty} \frac{f(x) - g(x)}{1} = 0$$ from which it is clear that $$…
Victoria
  • 365
1
vote
1 answer

Is $\log(3^n) = O(\log(2^n))$?

How can I prove that this is true/false: $$\log(3^n) \in O(\log(2^n))\ ?$$ I know $f(n)$ is $O(g(n))$ if there are positive constants $C$ and $k$ such that: $$f(n) \le C \cdot g(n)$$ whenever $n > k$. I think that the plot shows that it is not in…
Cal
  • 21
1
vote
2 answers

Big-oh and Small-oh Notation: Ratio.

Is it possible to say something about the order of ratios like $O(1/n^2)/o(1)$ or $O(1/n^2)/O(1/\sqrt{n})$?
rjann
  • 89
1
vote
2 answers

Show that $1^k+2^k+\cdots+n^k$ is $\Omega (n^{k+1})$

...where k is a positive integer. The Big Oh case is not so hard. But how do I show that $1^k+2^k+\cdots+n^k$ is $\Omega (n^{k+1})$?
Isa Hassen
  • 179
1
vote
2 answers

Analyze for loop with if statement

I have this rather complicated loop: sum=0 for i=1 to n do for j=1 to i^2 do if(j (mod i) = 0) then for k=1 to j do sum++ How the heck do I analyze this? I would try to use a sum but the if statement throws…
MortalMan
  • 157
1
vote
0 answers

Calculation of Running time of array when size increase by constant

I am learning data structure and running time calculation. I got a problem to understand the running time calculation of increasing the size of the array. 1) if we increase the size of the array by constant. $ N=4$ will be $ N_o$ $ N=8$ will…
Frq Khan
  • 113
1
vote
2 answers

Big O Definition

There is a formal definition for the Big O notation in Wikipedia. Up to now I have come across Big O in Numerical Analysis, Calculus and Algorithms which all are pretty distinct fields. What I am wondering is if that definition is global and is the…
Adam
  • 351
1
vote
2 answers

Laplaces Method not in standard form

I am trying to figure out the following integral to leading order $$I(x)=\int_0^{-\infty}dk\, \frac{e^{kx}e^{1/k}}{k^2}$$ I have thought about 2 different methods. The first is to consider $h(k)= e^{1/k}/k^2,g(k)=k$ So that $I(x)=\int…
yankeefan11
  • 1,449
1
vote
1 answer

Proving Asymptotic Barrier - O notation for $\ln(n!)$

I'm interested in the exact barrier of $$\ln(n!)= \Theta(n\ln(n))$$ and if it even exists. This means, there is a $c_1, c_2$ , so that $$\ln(n!) \le \Theta(n\ln(n) c_1$$ $$\ln(n!) \ge \Theta(n\ln(n) c_2$$ or $$0 \le \lim\limits_{n \to…
Somebody
  • 369
1
vote
1 answer

Hyperbolic sine and landau notation

I have given a function $f$: $$ f = \begin{pmatrix} \sinh(x_1 x_2) \\ \cosh(x_1 x_2) \end{pmatrix} $$ We have to show that this is possible: $$ f = \begin{pmatrix} 2x_1 x_2 \\ 1 \end{pmatrix} + \mathcal O \left( \|x\|^3 \right) $$ We have used the…
Martin Ueding
  • 4,523
1
vote
1 answer

Asymptotics behaviour of the sum

Let $S(n) = \sum_{k = n}^\infty \frac{ln^q k}{k^p}$, $p > 1$ How to determine asymptotic behaviour of the sum $S(n)$, ($n \rightarrow \infty$). The use of integrals doesn't solve the problem. Also I used Stolz–Cesàro theorem to solve the problem,…
J.Exactor
  • 215
1
vote
3 answers

Laplace's Method for Integral asymptotes when g(c) = 0

I am using these notes as my reference, but I am running into some questions. Say I am trying to find, for large $\lambda$ $$I(\lambda)=\int_0^{\pi/2}dxe^{-\lambda\sin^2(x)}$$ This has our maximum at $c=0$, where g(c)=0 and g'(c)$\neq$0. So when…
yankeefan11
  • 1,449
1 2 3
…
74 75