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
0 answers

Big-O estimation for $\frac{\log(\log(n^2+1)}{\log n}$

I think it should be like: $=\dfrac{\log(\log(n^2+10))}{\log(n)}$ $=\dfrac{\log(2\log(n))}{\log(n)}$ $=\dfrac{\log(\log(n))}{\log(n)}$ But $\log(\log(n))<\log(n)$ As the $log(n)$ is in the denominator. Hence it is $O(\log(\log(n)))$ Is it correct?
David
  • 153
0
votes
0 answers

Does there exist an asymptotic expansion?

Let $f(x) = \sqrt x $ and an asymptotic sequence is $\ x^n$ as x goes to zero. Does there exist an asymptotic expansion for f(x)?
CheersApp
  • 23
0
votes
2 answers

Prove $f(x)\sim ax^{n-m}$.

Prove if $f(x)$ is a polynomials with respective leading terms $ax^{n}$ then $$f(x) \sim ax^{n-m}$$ How do I approach this problem?
user511607
  • 93
0
votes
1 answer

How to find function growth in this asymptotic analysis problem?

Let $n=m!$ Which of the following is TRUE: $m=\Theta \left( \frac{\log n}{log \log n} \right)m=\Theta \left( \frac{\log⁡n}{\log⁡\log⁡n} \right)$ $m=\Omega \left( \frac{\log n} {\log \log n} \right)$ but not $m=O \left( \frac{\log n} {\log \log n}…
user292174
  • 171
0
votes
1 answer

Why Case 1 of Master Theorem for Asymptotic Analysis failed for This.

For $T(n) = 3T(n/3) + (n/2)$ with $a=3, b=3$ and $\log_3 3 = 1$ It's clear that $f(n) = \frac{1}{2}n$ is asymptoticaly slower than $f(n) = n^{\log_b a-e}$ for $e>0$ but the answer says it's case $2$. where i am wrong to solve this ?
user292174
  • 171
0
votes
2 answers

How do I go from the expression $(x+D)^{5/4} - (x)^{5/4} \sim P$ to $4/3Px^{-1/4}\sim D$?

$$(x+D)^{5/4} - (x)^{5/4} \sim P \qquad(x → ∞)$$ $$4/3Px^{-1/4}\sim D \qquad (x → ∞)$$ I was reading a text about asymptotic relation. How do we go from the first relation to the second relation? I tried using binomial theorem to expand the…
zhongyuan chen
  • 693
0
votes
1 answer

Prove that $(\log_2n)^{\log_2n} \in o(2^{(\log_2n)^2}) $

Let $f(n) = (\log_2n)^{\log_2n}$ and $g(n) = 2^{(\log_2n)^2} $ I want to show that $f(n) \in o(g(n))$. I guess it makes intuitive sense if we perform a a substitution $z = \log_2n$ we get $\lim_{z \to \infty} \frac{z^z}{2^{z^2}}$ which I remember as…
ghthorpe
  • 1,507
0
votes
1 answer

Find an example of function

Find an example of a function $f$ such that satisfies: $$\forall_{\varepsilon>0} \ f(n)=O(n^{1+\varepsilon})$$ but not $$f(n)=O(n)$$ I had been thinking about it for an hour and still can't find it. Can anybody help?
xan
  • 2,053
0
votes
1 answer

O-Notation Prove or Disprove $ 3^{O(n)} = O(8^{n})$

I am really new in data algorithm and Big O-Notation and could not find a good solution for this: $$ 3^{O(n)} = O(8^{n}) $$ First of all what does this term $ 3^{O(n)}$ mean? I thought using the definition of O-Notation: $f(n) \leq c g(n)$. But this…
Newuser1234567
  • 11
  • 1
  • 4
0
votes
2 answers

Simplify asymptotic expression $O (n) + n\cdot\log{(n)}$

I have an expression $$n\frac{10\log(n)+O(n)+4n}{O(n)+n\log(n)}$$ and I am not really sure about ${O(n)+n\log{(n)}}$ part. If I am adding $O(n)$, pr $O(n^2)$, $O(n\log n$ etc., to function $n\log(n)$, or $n^2$, $n$ etc. Are there same rules as for…
Reenergy
  • 11
  • 2
0
votes
1 answer

How to prove this equality, $log(O(5^{n})) = O(n)$?

How to prove this equality, $log(O(5^{n})) = O(n)$? If there was no big O notation in logarithm, my idea would be to take exponent $n$ and to put it in front of the algorithm, so we would get this: $n\log(5) = O(n)$ which, if my thinking is right,…
Tars Nolan
  • 387
0
votes
1 answer

Can the Big O relation be used to compare the values of a function at two different values of its variables?

Consider this Big O relation: $f{(s,t) }= O(t^{m(s)})$, where $0 < s < 1/2$ and $m(s)< 1/2$. Since ${t_2}^{m(s)} > {t_1}^{m(s)}$, for t_2 > t_1 does this imply that one has: $f(s,{t_2}) > f(s,{t_1})$ for ${t_2} > {t_1}$? Also, is this true for any…
Hass Saidane
  • 94
0
votes
1 answer

How to disprove $n^3 = \Omega(9^{\log_2(n)})$

I'm having trouble to disprove the following statement: $$n^3 = \Omega(9^{\log_2(n)})$$ I'm pretty sure that the claim is false but I'm struggling to falsify it in a formal way. I tried to calculate $$\lim_{n\to\infty}…
3nondatur
  • 4,178
0
votes
2 answers

How to show that $\log^n(n)=o(n!)$?

I am looking for a rigorous proof of $\log^n(n)=o(n!)$. I was thinking of using this property: If $f(n), g(n) \geq 1 \ \forall\in \mathbb{N}$, and $\log f(n)=o(\log g(n)),$ then $f(n)=o(g(n)).$ However, $\log^n(n)=0$ for $n=1$, so I don't know what…
Hodin
  • 51
  • 4
0
votes
2 answers

big o notation of fraction $\frac{\log(N+1)}{\log(N)}$

I want to estimate big-O notation for $\frac{\log(8n^2)}{\log(n)}$. I think the big-O notation is constant. am I right? in case of $\frac{\log(N+1)}{\log(N)}$, is it the same and O(1)? and what about $\frac{\log(N^3+7n+1)}{\log(N^4+N^2)}$, is it…
David
  • 153
1 2 3
…
74 75