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

Find functions $f(n)$ and $g(n)$ such that $f(n)\in\Omega(g(n))\setminus\Theta(g(n))$, but $\lim_{n\to\infty}$ does not exist.

I found an answer but I'm not sure if it is correct: Let $f(n)=(2+\sin n)\cdot n$ and $g(n)=\ln n$. $0\leq g(n)\leq f(n)$ $\forall n\gt0$ so $f(n)=\Omega(g(n))$. But $f(n)\neq\Theta(g(n))$ because $f(n)$ will always grow faster than $g(n)$…
Revoltechs
  • 321
  • 1
  • 9
1
vote
2 answers

Find asymptotically equivalent function for $\ln \binom{n^2}{2n}$

How can I find an asymptotically equivalent function for $\ln \binom{n^2}{2n}$? I think I need to use the definition of the binomial coefficient and Stirling's approximation, but I'm not sure what to do after this.
ijk
  • 17
1
vote
2 answers

Equations in Landau/ Big O Notation

$ \underbrace{x^2 +x + O(\epsilon^2) = 0}_{\mathrm{equation \ 1}} \implies \underbrace{x^2 + x = O(\epsilon^2)}_{\mathrm{equation \ 2}} $ I'm asked why there isn't any need to write $-O(\epsilon^2)$ for the second equation. All I can think of is…
Marc
  • 25
1
vote
1 answer

How to prove whether $\frac{\sqrt{n}}{\log_2n}$ is in $O(n^{1/3})$?

How to prove whether the statement is true or not: $$\frac{\sqrt{n}}{\log_2n} = O(n^{1/3})$$? I know for a fact that the statement is false. The prove doesn't have to be rigorous, I simply have to convince someone of the validity of the statement.…
Sebastian Nielsen
  • 612
1
vote
1 answer

Prove an equivalence of asymptotic formulas

I have the following: $$\Omega\left(\frac{\log N}{\log\log N}\right)\leq n.$$ The claim is that this implies $$N\leq n^{O(n)}.$$ I have made no progress on proving that this is true. Does anybody have an idea of where to start? Thanks in advance.
Drew Meier
  • 109
  • 7
1
vote
0 answers

What is a Big-O of a little-o function?

I have a statement involvinga function $f(\tau)=\mathcal O(H(\tau))$, and I could show that this function $H(\tau)$ satisfies $\lim_{\tau\to\infty}H(\tau)=0$. So I can say that $H(\tau)=\mathcal o(1)$, correct? If so, would this then imply that…
Britzel
  • 299
1
vote
2 answers

What does $n_0$ mean when describing Big-O notation?

When defining the "Big-Oh" notation, we say that $f(n) \text{ is } O(g(n))$ if there is a real constant $c > 0$ and an integer constant $n_0 \geq 1$ such that $$f(n) \leq c \cdot g(n), \text{ for } n \geq n_0$$ For this definition, what is the…
Serrano
  • 131
1
vote
1 answer

prove or disprove: if $f$ and $g$ are monotonic increasing, then $f(n)=O(g(n))$ or $g(n)=O(f(n))$

I'm trying to prove (or disprove) that if $f$ and $g$ are monotonic increasing, then $f(n)=O(g(n))$ or $g(n)=O(f(n))$ but with no success. Can someone help me with this? thanks.
Noa1996
  • 31
1
vote
1 answer

Asymptotic behavior of equation$ O(n\log n)=O(n^{1.1})$

The following equation should be true: $O(n\log(n))=O(n^{1.1} )$ Based on the following article, one should see the equation as the left part being an element of the right part. What are the rules for equals signs with big-O and little-o? Given that…
Stef
  • 13
1
vote
0 answers

Finding closed form of for loop to get big o

I came across this problem for (int i = n; i > 1; i = i / 4) { for (j = 0; j < n; j++) { F() } } and I need to find the closed form for how many times F() is called so I can get the big o of it. I'm pretty sure it is O(n*log(n)), but…
mymemesarespiciest
  • 295
  • 2
  • 10
1
vote
1 answer

What's the difference in these two definitions of little-o (from CLRS vs. Wiley algorithms books)?

Algorithm Design: Foundations, Analysis, and Internet Examples by Goodrich and Tamassia (Wiley, 2002) defines little-o as follows: $o(g(n)) = \{ f(n) : \forall c > 0,\ \exists n_0 > 0\ \text{such that } \forall n \geq n_0,\ 0 \leq f(n) \leq cg(n)…
Heather Guarnera
  • 538
1
vote
1 answer

Is my Big Oh proof correct?

I need pointers or corrections on my proof procedure. Prove $x^2 + 2x + 1 \in O(x^2)$: $x^2 + 2x + 1 \le cx^2$ $1+2/x+1/x^2 \le c$ This inequality holds for $x \ge 1$ and $c \ge 4$. Thus $x^2+2x+1 \in O(x^2)$
user52272
1
vote
2 answers

Do asymptotic functions have asymptotic definite integrals?

If $f(x) \sim g(x)$, and $$ I_f = \int_{0}^{t} f(x)dx $$ and $$ I_g = \int_{0}^{t} g(x)dx $$ then does $I_f \sim I_g$ (as $t$ goes to infinity) hold? If not, in what situations does it not hold? How would one go about proving such a relation?…
Nine Thousand
  • 731
1
vote
0 answers

Particular form of Asymptotic solution to ODEs

I am currently reading Heisenberg's PhD thesis. There is a common technique in fluid dynamics which keeps cropping up and I can never get my head around. The equation of interest is the Orr-Sommerfeld equation $(\phi '' - \alpha^{2}\phi)(w-c) -…
Andy
  • 55
1
vote
0 answers

Big and Small O Notation

I am currently trying to learn the meaning of the Landau Symbols a bit better by solving exercices, namely the following three: $f_1(x) + f_2(x) = O(g_1(x) + g_2(x))$ given that for each f(x) the property already holds $n!n^{s} = o(n^n)$ for $n…
user66280
1 2 3
…
74 75