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

What is the Big-$O$ of $\prod_{i=2}^n log{(i)}$

As I can see $$\prod_{i=2}^n log{(i)} = log(2) \cdot log(3) \cdot log(4)...log(p) \cdot log(p+1) ... log(n)= O(k^n)$$ when $$ log(p) = k$$ Am I right? Is there any better Big-$O$ for it?
ChaosPredictor
  • 303
  • 3
  • 12
1
vote
3 answers

Big-O and Big-Theta of $\sum_{i=0}^{n}{\binom{n}{i}i}$

I'm trying to find upper and lower limit of: $\sum_{i=0}^{n}{\binom{n}{i}i}$ At the moment the only idea I have is: $\sum_{i=0}^{n}{\binom{n}{i}i} \ge \sum_{i=0}^{n}{\binom{n}{i}} = 2^n$ Any other suggestion to Big-$O$ & Big-$\Theta$?
ChaosPredictor
  • 303
  • 3
  • 12
1
vote
1 answer

Increasing functions $f,g$, and asymptotic of $\max(f(n),g(n))$

I'm new to introduction to algorithms and asymptotic analysis. I'm trying to prove/disprove this: Let $f,g\colon\mathbb{N} \to \mathbb{N}$ be increasing functions, i.e. such that $(f(n+1)>f(n)$ and $g(n+1)>g(n))$ for all $n$. Define…
joe
  • 111
1
vote
0 answers

Worst case of Shell Sort?

What is the worst case for Shell Sort? I think worst case is an ordered set with the largest values in odd positions: $$ 1,4,2, 16,8, ...$$ With $O(n(log$ ${n)}^2)$ complexity or $O(n^2)$? Actually, I think that the former one is correct as opposed…
David
  • 153
1
vote
0 answers

Asymptotics on Golden Ratio/Fibonacci

Given Fibonacci is F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) for all n >= 2 Prove that for any a, b such that 1 ≤ a < φ < b we have that F(n) ∈ O(b^n ) and that F(n) ∈ Ω(a^n ). I'm looking for help on how to start this question
s878
  • 11
1
vote
1 answer

Why is $3^n$ = $2^{O(n)}$?

I read that $3^n$ = $2^{O(n)}$. But shouldnt having a base 3 be exponentially larger than having a base 2 ?
Link L
  • 717
1
vote
1 answer

Manipulating a series of big theta functions

I am trying to understand the process of finding the complexity of a nested for loop. I understand all the steps of the solution provided, except for one which I find unintuitive: $$\sum_{j=1}^n \Theta(j^2) = \Theta\left(\sum_{j=1}^n j^2\right) $$…
Cyruno
  • 65
1
vote
4 answers

Big $\mathcal{O}$ notation problem

I need to show that the function $f(n) = n^2$ is not of $\mathcal{O}(n)$. If I am correct I should prove that there is no number $c,n \geq 0$ where $n^2\lt cn$. How to do that?
Fazlan
  • 297
1
vote
1 answer

Clarifying the definition of big-oh

I am a computer science student and I am familiar with big-oh notation in algorithm analysis books. But the book I am working for mathematical analysis is using somewhat different asymptotics definitions to analyze vanishing rate of the error term…
meguli
  • 640
1
vote
4 answers

Big O notation example.

Why is $n^{1000} \in O(5^{\sqrt{n}})$? I thought that since $5^{\sqrt{1000}} < 1000^{1000}$ then it would be the otherway around. Could you please give me the mathematical derivation of this? Thanks in advance
DariusTheGreat
  • 426
1
vote
0 answers

Given $f(x)$ and asymptotic series $\phi_n(x)$ how to determine if expansion exists?

Given a function $f(x)$ and an asymptotic series $\phi_n(x)$ as $x\rightarrow x_0$. What is the easiest way to determine if the asymptotic expansion of $f(x)$ exists when using the series $\phi_n(x)$?
Quantum spaghettification
  • 2,362
1
vote
1 answer

Showing that $O(o(f))=o(O(f))=o(g)$ if $f=O(g)$

In Asymptotic Analysis by J.D.Murray on page 10 the following question is posed. If $f=O(g)$ show that: $$O(o(f))=o(O(f))=o(g)$$ I am really confused by what this actually means. How can you have $O(o(f))$? Surely $O$ has to act on a function and…
Quantum spaghettification
  • 2,362
1
vote
1 answer

Asymptotes cuts curve in eight points which lie on a circle of radius unity

Show that the four asymptotes of the curve $(x^2-y^2)(y^2-4x^2)+6x^3-5x^2y-3x^2y+2y^3-x^2+3xy-1=0$ cut the curve again in eight points which lie on a circle of radius unity. I have found the asymptotes to be $y=x; y=-x-1; y=2x; y=-2x-1$. Then I…
user464068
  • 91
1
vote
0 answers

What is the order of this expression?

Suppose I have $$C^2D^2 + C^4 - 2C^3D$$ where $C$ and $D$ are small numbers. The order should be worst case scenario, I am unsure how to write it. Can I say it's "order 2 in $C$" and "order 1 in $D$" even if they correspond to different terms?
markclops
  • 33
1
vote
1 answer

Asymptotic problem and $\Theta$ notation

We have two positive and increasing integers $a$ and $b$. We assume that $a$ is a function of $b$ and that we have: $$a \log a \sim b$$ where $\sim$ is the asymptotic equivalence. I would like to show that $a = \Theta(\frac{b}{\log b})$. Thank you.
Dingo13
  • 435
1 2 3
…
74 75