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
1 answer

Showing $n^{\log{n}} = o(2^n)$

I would like to show that $n^{log n} = o(2^n)$. Here is my attempt: I see that $\log{(n^{\log{n}})} = (\log{n})^2,$ and $\log{2^n} = n\log{2}$. I also know that $(\log{n})^2=o(n)$, so that for any $d>0$ eventually $(\log{n})^2 < d{n}.$ So, one…
MathStudent
  • 1,352
  • 11
  • 22
1
vote
0 answers

Is $f(n)=O(g(n))$ or $f(n)=\Omega(g(n))$ when $f(n) = (\log n)^{\log n}$ and $g(n) = n/\log n$?

I have showed that $f(n)=\Omega(g(n))$ in the following way. We assume that $${\log n}^{\log n} \leq n/\log n$$ $$\implies \log n \times \log \log n \leq \log n - \log \log n$$ $$\implies \log \log n…
aghost
  • 559
1
vote
1 answer

for [ f(n) = Sum(1:n) , g(n) = n^2 ] , why does ( f isIn O(g) AND g isIn O(f) ) hold?

An exercise solution claims that for f(n) = Sum(1:n) , g(n) = n^2 it holds that f isIn O(g) and g isIn O(f). I don't understand why this is, as it seems to me that f isIn O(n) and g isIn O(1), because f contains n loop iterations while g contains a…
uigv
  • 11
1
vote
1 answer

peak limiting/audio compression formula needed

I'm looking for a formula to effectively compress an audio waveform to limit peaks. This isn't an "automatic volume control" application where one would control amplifier gain to maintain a volume level, but rather I want to limit ("soft" truncate)…
Daniel R Hicks
  • 514
1
vote
1 answer

Define function F which is big O but not big theta

Searching for one definition of $f : \mathbb{N} \rightarrow \mathbb{N}$ with $f' : \mathbb{N} \rightarrow \mathbb{N} $ defined with $f'(n) := f(n+1) - f(n)$ with the bounderies $f=O(f')$ and $f \not= \ \theta(f')$ Definition: $f=O(f')…
Roby
  • 125
  • 3
1
vote
0 answers

Mutual Asymptotic analysis of the given fucntions

$ f(n)$ = $ 3n^{\sqrt{n}} $ $g(n)$ = $2^{\sqrt{n}log_2n}$ $h(n)=n! $ For all the $3$ pairs of the functions, which one is $Big-O$ of which ? I am unable to compare these functions. Edit : I plotted them and observed that for large $n$ :-…
PleaseHelp
  • 761
  • 8
  • 29
1
vote
1 answer

Arrange in increasing order of asymptotic complexity

I have to arrange the above time complexity function in increasing order of asymptotic complexity and indicate if there exist functions that belong to the same order. So, my answer is $[lg(n)]^2$ $lg(2^n)$ and $log(2^n)$ and $2^{lg(n)}$ these…
LeonBrain
  • 159
  • 1
  • 6
1
vote
0 answers

Calculate the leading-order asymptotic behaviour (Laplace's Method)

thanks in advance! Calculate the leading-order asymptotic behaviour of the integral $$I(x) = \int_{0}^{2\pi} (1+t^2) e^{x \cos t} dt \mbox{ as } x \mbox { tends to infinity}$$ So far I know there are two maximas at $0 \mbox{ and }2\pi$ so it can be…
Dan
  • 11
0
votes
1 answer

Asymptotic expansion of $\sin\left(\pi + \exp(-1/\epsilon)\right)$

I need to find the two term asymptotic expansion of $\sin\left(\pi + \exp(-1/\epsilon)\right)$ as $\epsilon$ tends to zero, but the exponential term is confusing me...
Martin MacDonald
  • 1
0
votes
1 answer

If some function f is in big O(some function g), do f and g necessarily need to have the same domain and codomain?

Say I have a function, $g:\mathbb{R} \mapsto \mathbb{R}$. Then would the set $O(g)$ be defined (as explicitly as possible) as: $$O(g) = \{ f:\mathbb{R} \mapsto \mathbb{R} \space|\space \exists C \in \mathbb{R}^{+}:\exists n_{0} \in \mathbb{R}:…
James Hiew
  • 155
0
votes
1 answer

Meaning of the $\{1 + o(1)\}$

Being a software developer, I have the basic understanding of big-O and small-o notation. But currently I've faced set of mathematical problems, where they operate with asymptotics on much more advanced level. Getting to the point: What intuition…
Dmitri K
  • 1,401
0
votes
2 answers

Big-Oh Notation and Solving for f(x)

Taking Discrete Mathematics and completely lost when it comes to Big-Oh Notation. While I know it's used to profile code I can't figure out how to solve the following problem: Find the least integer $n$ such that $f(x)$ is $O(x^n)$ for each of these…
sheppardzw
  • 111
0
votes
2 answers

How can I prove that "n is not O(1)"?

I want to prove that $f(n) \neq O(g(n))$ when $f(n) = n$, $g(n) =1$ precisely. I can prove correct big-Oh expression such as $n = O(n)$, $\lg(n) = O(n)$ etc. but I can't prove incorrect big-Oh expression like above. How can i prove such thing? p.s.…
Won Seok Lee
  • 49
  • 1
0
votes
1 answer

Why does $f(n) = O(n^2)$?

My book says: For example, consider $f_1(n) = n$ and $f_2(n) = n^2+1$. Clearly, the former is $O(n^2)$ and the latter is $O(n^3)$. I thought they would both be $O(n)$ and $O(n^2)$ respectively. Why is it "clear" that these two have the complexity…
user6607
  • 381
0
votes
2 answers

Show that $f(x) = x^2 + 5x + 9$ is $O(x^2)$.

Show that $f(x) = x^2 + 5x + 9$ is $O(x^2)$. This involved the big O notation. I can understand a bit of big O notation but answering this question to me is difficult. None of the examples I have come across are working out for me. Can someone tell…
Sumeet
  • 1
1 2 3
…
74 75