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

Prove that for all functions $g: N \to R^{\geq 0}$, and all numbers $a$ in $R^{\geq 0}$, if $g \in \Omega(1)$ then $a + g \in \Theta(g)$

Here is a more readable version of the question: Prove that for all functions $g: \mathbb{N}\to\mathbb{R}^{\geq 0}$, and all numbers $a \in \mathbb{R}^{\geq 0}$, if $g \in \Omega(1)$ then $a + g \in \Theta(g)$ What I've done so far: In order for $a…
user712456
2
votes
1 answer

Time complexity and proof of time complexity

Which is true and which false? I can't really decide which one is true and which false. Maybe in first 3 cases. $$3n^5 − 16n + 2 \in O(n^5)$$ $$3n^5 − 16n + 2 \in O(n)$$ $$3n^5 − 16n + 2 \in \Omega(n^{17})$$ $$3n^5 − 16n + 2 \in \Omega(n^5)$$ $$3n^5…
Supermartzin
  • 179
2
votes
1 answer

An asymptotic expansion for MeijerG function

By using Mathematica Series[MeijerG[{{-(1/2)}, {}}, {{-(1/2), -(1/2), 1/2}, {}}, a x], {x,0, 0}, Assumptions -> a > 0], I got an asymptotic expansion of MeijerG function at $x\approx 0$ for $a>0$ as $$G_{1,3}^{3,1}\left(a x\left| \begin{array}{c} …
Frey
  • 1,103
2
votes
2 answers

Finding the asymptotes of $(y-a)^2(x^2-a^2)=x^4+a^4$.

Problem: Finding the asymptotes of $(y-a)^2(x^2-a^2)=x^4+a^4$. My efforts: $(y-a)^2(x^2-a^2)=x^4+a^4\implies (y-a)^2=\dfrac{x^4+a^4}{x^2-a^2}\implies x=\pm a$ are vertical asymptotes. What are the remaining asymptotes?
PrimoRaj
  • 357
2
votes
2 answers

Rate of growth of exponential and factorial

I am trying to determine which function grows faster: $g(n) = n^{({\ln n})^n}$ or $f(n)=(n!)^{2^{n}}$. Based on intuition, my idea was to compare either bases or powers and hopefully to find which function grows faster, but that's not the case…
mark.keane
  • 199
2
votes
2 answers

$T(n) = 2T(n/2) +\lg(n!) $ asymptotic bounds

$T(n) = 2T(n/2) + \lg(n!)$ What are the upper and lower bounds of this equation?
Sara Meyer
  • 101
2
votes
1 answer

Proving that $\log(n!)$ is $O(\log n^n)$

I am trying to prove that $\log(n!)$ is $O(\log n^n)$ and I have an intuition for it, but I can't seem to find the constant $c$ that would make $\log(n!) < c \cdot \log(n^n)$ for all $n > n_0$. As of now my idea is that we could split $\log(n!)$…
dl2022
  • 21
2
votes
1 answer

Growth rate of $(n!)!$ vs $((n-1)!)!\ (n-1)!^{n!}$

Which function grows faster: $(n!)!$ or $((n-1)!)!\ (n-1)!^{n!}?$ [Show using logarithms.] This is exercise 2(c) from chapter 9 of Concrete Mathematics (Knuth, Patashnik, Graham). A few computer calculations and one can see that the former grows…
Marwan Mizuri
  • 182
2
votes
1 answer

Asymptotic order

Below is a question I faced from an online test for preparation of exam and I had doubt in solution provided so I wanted to discuss my approach and ask about it. $$\frac{e^{n\log n}}n(A),n^{\sqrt n}(B),2^{n\log n}(C)$$ I want to order these…
user3767495
  • 781
2
votes
2 answers

Little-oh vs. $\ll$ notation

Let $a_n$ and $b_n$ be two sequences. I'm trying to understand the difference between $a_n = o(b_n)$ and $a_n \ll b_n$. $a_n = o(b_n)$ as $n \to \infty$ if $a_n/b_n \to 0.$ $a_n \ll b_n$ if $a_n \ge 0$ and $a_n = o(b_n).$ What is the importance of…
theQman
  • 1,097
2
votes
0 answers

Order of Growth Definition

According to this book (section 3.1 Order of growth): An order of growth is a set of functions whose asymptotic growth behavior is considered equivalent.  I'm trying to find more precise definition about order of growth. If I understand author's…
No Name QA
  • 163
2
votes
1 answer

Prove $f(n)=n \log{\log{n}} \notin \Theta (n^k)$ for any $k$

How do I prove $f(n)=n \log{\log{n}} \notin \Theta (n^k)$ for any $k$? I have no idea where to start but I tried plotting the graph in Google and noticed that $\log{\log{n}}$ is very close to 0. But might it be because it doesn't have a lower…
Jiew Meng
  • 4,593
2
votes
1 answer

Big O and Big Omega

For a homework problem, we've been asked to prove the following: $$6n^2+20n \in O(n^3)$$ $$6n^2+20n \not \in \Omega(n^3)$$ Since BigO is defined as $g(n) \leq c \cdot f(n)$ for a function $f(n)$, set of functions $g(n)$, some real constant $c$ and…
Jason
  • 1,191
2
votes
1 answer

Asymptotic Expansion of Integrals in general form

How to understand asymptotic expansion of $$ I(s) = \int_0^1 \frac{dx}{\sqrt{1+s f(x)}}$$ where $f$ is periodic of period 1, $f(x) \geq 0$ as $s\longrightarrow \infty$?
Sean
  • 1,433
  • 12
  • 16
2
votes
2 answers

"Big-Oh" notation applied to sum

This is the definition of the $\mathcal{O}$ notation in my textbook: And I need to show the following: Intuitively, I understand what the proposition tries to say is that because $|f(n)| \leq C . g(n) \, \forall n \geq n_o $, the difference…
ensbana
  • 2,277
1 2 3
…
74 75