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

Using the squareroot on small o (landau notation)

Suppose $k\rightarrow\infty$, and $\sqrt(\frac{1}{x_k})=o(y_k)$, is it then true that $\frac{1}{x_k} =o(y_k)$? $x_k\rightarrow\infty$ and $y_k\rightarrow 0$, if it helps. Help would be appreciated.
blubby
  • 45
0
votes
1 answer

Big-theta of $\log^2(n)$

I have been trying to understand weather I can reduce this to more simple possible terms? : $$\Theta(n^3)+\Theta(n^2 \log^2(n))$$ I know that $O(\log^2(n))=O(n^a)$ for $a > 0$. But I'm not sure if that true with theta notation.
Anirudh Gangwal
  • 133
0
votes
1 answer

Properties of $\mathcal{o}$ notation

I have some trouble understanding how $\mathcal{o}$-notation works. Take for example $f \in \mathcal{o}(n^{-1/2})$. Then what would the limiting behavior of $nf$ or $f^2$ be? Can somebody explain this to me?
Sarah2108
  • 1
0
votes
1 answer

Is $\log(\sqrt{n}) = O(\log(n))$?

I'm studying asymptotic analysis and I have a doubt about this comparison. So, is $\log(\sqrt{n})$ thus $\log(n^{1/2}) = O(\log(n))$? Or are they asymptotically equivalent?
Simone C.
  • 225
0
votes
1 answer

Is $n \log_{2}n$ a little-o bound for $n \log_{10}n$?

If I have the function $$f(n)=n \log_{10}n$$ Is it correct to say that the asymptotic bound, in little-o notation, for $f(n)$ is $o(n \log_2n)$? $~\forall~n>0$, $n \log_2n$ would strictly be an upper bound for $n \log_{10}n$, but does this meet…
tpm900
  • 139
0
votes
1 answer

Can Stirling's approximation be used to show that the Binomial distribution is asymptotically equal to the Poisson distribution?

I've been thinking about a basic question recently. It is well known that the Bernoulli distribution $$p_k = {N \choose k} p^k (1-p)^{N-k} \tag{1} $$ asymptotes (i) to a Gaussian distribution if $p=const$ and $N\to\infty$ (also $1\ll k \ll N$) and…
Cyclone
  • 1,853
0
votes
1 answer

Solving Recurrences - find an asymptotically right bound

I find this question very tricky: Got stuck very fast after the basics- I have been on this for too long. Help will be much appreciated.
sheldonzy
  • 667
0
votes
1 answer

How to find asymptotes

I'm supposed to find asymptotes for $x\cdot\arctan(x)$ for a homework assignment. Are there any theorems regarding this I can utilize to find the equation for the asymptotes, or is this one of those solve case by case things, where this particular…
Andreas Hagen
  • 453
  • 1
  • 3
  • 12
0
votes
1 answer

What is the order of $\sum_{i=1}^{n-1}(n-i)(k-i)\log(k-i)$?

Let $n
drzbir
  • 496
  • 4
  • 19
0
votes
2 answers

Proving Big Oh with Hierarchy Theorem

I need help with proving that $$ 100n^2+(0.5)^{15^{15^{15}}} \cdot 2^n = O(2^n).$$ I started by using the definition: There should exist $c$ and $n_{0}$ in the positive reals such that, for all $n$ in the naturals, $$n\geq n_{0} \implies…
soka
  • 43
0
votes
1 answer

Asymptotic expansion of exponential integral $\int_ 0^1 \frac {e^{-t} dt} {1+x^2t^3}$

How to find the full asymptotic behavior of $$\int_ 0^1 \frac {e^{-t} dt} {1+x^2t^3}$$ as $x$ tends to $0^+$ ?
Hei709864
  • 43
0
votes
1 answer

Proving asymptotic relations between two functions

Is $n^a \in O(b^n)$, where $O(\ast)$ represents asymptotic notation? We only requre $a \in \mathbb R$ and $b > 1$. Would appreciate the help! Thanks.
dawnoflife
  • 101
0
votes
1 answer

Finding the order of magnitude of functions as ϵ tends to zero

find the order of magnitude of the function sinh $\frac{1}{ϵ}$ as ϵ tends to zero. The answer is suposed to be in terms of exponential function but when you look at the maclaurin series and replace the x with $\frac{1}{x}$ it becomes infinite and…
Shiguftah
  • 1
0
votes
1 answer

finding asymptotically tight bound

I'm Reading Introduction to Algorithms and in the section where they talk about how any quadratic function $$f(n) = an^2 + bn + c$$ where $a$, $b$ and $c$ are constants and $a > 0$ Throwing away the lower-order terms and ignoring constants yields…
Rockstar5645
  • 169
0
votes
1 answer

Homework Assignment on Asymptotics

I recently did a homework assignment and got zero credit on a question. I would really like to know how to prove this question. I will show my solution and I would like to know what I did wrong and what I should have wrote. Prove that…
InsigMath
  • 2,073
  • 2
  • 18
  • 27
1 2 3
…
74 75