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
2
votes
2 answers

How to prove that $2^{n+1} = \Theta(2^n)$?

I have a problem were I need to prove big theta. $f(n) = 2^{n+1} = Θ(2^n)$. I proved that this was true for big O but I'm not sure how to go about proving big Theta.
John
  • 71
2
votes
1 answer

Confusion about Big O notation

I have a somewhat stupid question regarding the "Big O" notation: Is there any difference between saying $f=O(g)$ and $f\le O(g)$?
qmaster
  • 63
2
votes
2 answers

Proof $10n = O(n^2)$

As it says in the question name. I want to proof this big-o notation: 10n = O(n^2) Is this way here the correct an proper way to do so? n0 = 0 10n = O(n^2) n = O(n^2) for N n > 0 n + 1 ≤ (n+1)^2 n + 1 ≤ n^2 + 2n + 1 n ≤ n^2 + 2n I feel not 100%…
TacoVox
  • 21
2
votes
2 answers

determining the order of expressions, eg: $\sqrt{\varepsilon(1-\varepsilon)}$

I have to determine the order of loads of expressions as $\varepsilon \to 0$. Can you help me by giving me an example of how to find the order of $\sqrt{\varepsilon(1-\varepsilon)}$.
steven
  • 135
  • 2
2
votes
2 answers

Showing something is an asymptotic sequence

I need to show that $\phi_n(z)=\ln(1+z^n)$ as $z \rightarrow 0$ is an asymptotic sequence, i.e. to show that $$\lim_{z\rightarrow 0}\frac{\phi_{n+1}(z)}{\phi_n(z)}=0.$$ Is it sufficient for me to say that as $z\rightarrow 0$,…
Heijden
  • 331
  • 1
  • 3
  • 12
2
votes
1 answer

Order of logarithmic functions as $x \rightarrow 0$

I am trying to find the order of logarithmic expressions as $x \rightarrow 0$. For example I can find that $\ln(1+x) = \mathcal{O}(x)$ and $\ln(1+x) = \mathcal{o}(1)$. But when dealing with more complicated expressions below: $$\ln\left[…
Heijden
  • 331
  • 1
  • 3
  • 12
2
votes
1 answer

Asymptotic sequence of tan(z)

I have a question about the asymptotic sequence of $\tan(z)$: $$\tan z \sim ~ z+\frac{1}{3}z^3+\frac{2}{15}z^5 $$ $$\sim~ \sin z+\frac{1}{2}\left(\sin z\right)^3+\frac{3}{8}\left(\sin z\right)^5$$ I have a problem with the second sequence in…
yarnamc
  • 709
2
votes
0 answers

Asymptotic for degree

How can I find asymptotic for $\chi(n)$, if $\chi^{\chi^\chi} = n$. Is here self-qualification estimation? I tried to take the logarithm of both sides, but to nothing has come.
neznaika94
  • 167
2
votes
3 answers

Is there a function thats not in Big O and not in Big Omega?

I've been thinking about this problem for a while now but I can't fully come up with an example. It would make sense that this would exist and the only way I think it would work is if the functions were oscillating up and down and you could never…
user195778
2
votes
1 answer

Subtraction of functions with BigO

When trying to assess the Big $O$ of two functions that are added together, we take the max of the two. What happens if there is subtraction instead of addiiton? for instance: $$f(n) = O(n^3) $$ $$ \text{and} $$ $$g(n) = O(n^3)$$ then $$ (f-g)(n)$$
RustyShackleford
  • 525
2
votes
1 answer

Max of functions are in big O of the sum of their individual big Os

$\max(f(n), g(n)) = O(f(n) + g(n))$ How do I prove this? Also I'd appreciate the markup being corrected, thanks.
Matt Joiner
  • 121
2
votes
1 answer

Asymptotics of $\frac{1}{n} \sum_{ d|n } \mu{\left(\frac{n}{d}\right)} 2^d $

Define $$a(n) = \frac{1}{n} \sum_{ d|n } \mu{\left(\frac{n}{d}\right)} 2^d $$ where $\mu()$ is the Möbius function. Is it possible to find easily computable $b, c$ such that $b(n) \leq a(n) \leq c(n)$ for all large enough $n$ such that $$\limsup…
user66307
2
votes
1 answer

Prove $O(x)+O(x^2)=O(x^2)$ (Big O Notation)

I have to prove: $O(x)+O(x^2)=O(x^2)$ for $x\to\infty$ where "O" is the Big-O-Notation Specific functions are no problem for me, but I have some difficulties with this general form. But nevertheless I tried the following: $O(x)$ means $|f_1(x)|\leq…
ulead86
  • 3,381
1
vote
1 answer

Landau Big O, Little o notation, complex example

I stumbled upon a set cardinality asymptotics: $$O(n^{o(1)}),$$ I have a problem interpreting it. Can somebody give me a hint how to look at it?
hungry91
  • 13
1
vote
3 answers

O-Notation: How to put the function in order.

I am new here, so I am sorry for any mistake that I'll probably make. I have an exercise to solve, but I didn't really understand how this really works. I am given the functions $2^n$, $n^{0.01}$, $\log n$, $\log(n^3)$, $n \log n$, $n^n$, $1$, $\log…
savyia
  • 11
1 2 3
…
74 75