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

Is it true that $\dfrac{n}{2\sqrt{n}-1}=\Theta(\sqrt{n})$?

I have a function of the form $$f(n)=\dfrac{n}{2\sqrt{n}-1}.$$ I would like to find the big-O of this function (or big-Theta). How can I find these? I tried this method: Multiply both the denominator and the numerator by $\sqrt{n}$. I…
zdm
  • 452
1
vote
1 answer

Which mathematic skills are necessary to understand big-o notation on a basic level?

I am trying to wrap my head around big O notation and am quickly stuck just trying to understand the the mathematical jargon that is thrown around. It has been a long time since I touched that type of math and therefore need a refresher course.…
zeckdude
  • 127
1
vote
1 answer

How to prove (or disprove) this Big Oh relationship

If we let $f(n)), g(n)$ be two non-negative and monotonically decreasing functions such that $f(n) = O(g(n))$, how can I prove that $\log_2(f(n)) = O(\log_2(g(n)))$? Is this even true in all cases? I am not sure if I am allowed to just apply the…
Harrison W.
  • 777
1
vote
3 answers

Is $(n^{\ln n}) ∈ O((log_2(n))^n)$?

Given: $f(n) = n ^ {ln (n)}$ $g(n) = ( log_2n )^n$ Is $f(n) \in O(g(n))$, $g(n) \in O(f(n))$, or neither? Why?
Tin Man
  • 121
  • 3
1
vote
0 answers

Getting the two highest order terms in the sum $\sum_{j=0}^n j^k \left(\frac{n^2}{j(n-2)}\right)^j$

How to get the two highest order terms in $$ \sum_{j=0}^n j^k \left(\frac{n^2}{j(n-2)}\right)^j, $$ where $k\in \mathbb{N}$, leaving the rest in big Oh of something. I think this sum equals $$ n^k \left( \frac{n^2}{n-2}\right)^n +…
Teddy
  • 2,396
1
vote
1 answer

Small doubt regarding asymptotics

This is possibly a duplicate, but I couldn't find the answer to it. For example, if we have $lg(n!) = \theta ({n lg n})$, then can we sustitute $n$ with any other function? Like putting $n=n!$ will make it: $lg((n!)!) = \theta ({(n!) lg (n!)})$. If…
shiva
  • 492
1
vote
0 answers

What is a convenient solution to the inequality $x>y+z\log x$?

The inequality $$ x > y + z\log x $$ appears often when analyzing two objects with some different asymptotic rates, and I find myself staring at this "Lambert W" style of inequality very often in computer science and statistics. For $y,z>0$, is…
VF1
  • 1,993
1
vote
1 answer

Definition of order of magnitude (Big Oh)

In control theory, the order of magnitude notation $\mathcal{O}(\varepsilon)$ is usually defined as: $f(\varepsilon)=\mathcal{O}(g(\varepsilon))$ if there exist positive constants $k$ and $c$ such that $|f(\varepsilon)|\leq k|g(\varepsilon)|$,…
M3053
  • 184
1
vote
1 answer

Implications using Landau-Notation

Let $$ f(x)=1+\frac{\log x}{x}+o\left(\frac{\log x}{x}\right), x\to\infty. $$ Do we then have $$\lim_{x\to\infty}x\log(f(x))=\infty?$$ My answer would be yes, since: First of all, I think that we have $$ f(x)\sim 1+\frac{\log x}{x},…
Salamo
  • 1,094
1
vote
2 answers

Need help proving an asymptotic notation

I am studying for National Olympiad for informatics and one of the questions was about asymptotic notations. The equation was this: $$ log5^+4∈Ω() $$ I am a high school student and haven't learned logarithm yet; but I tried my best, only to find…
AliTeo
  • 51
1
vote
1 answer

Find the smallest integer constant $c$ such that $f(n) = \mathcal{O}(n^c )$

Find the smallest integer constant $c$ such that $f(n) = \mathcal{O}(n^c)$. There are two parts to this. In the first part, $f(n) = \dfrac{n^2}{2}$. From what I understand, if $f(n) = \mathcal{O}(n^c)$, then $$\dfrac{f(n)}{n^c} \leq x \implies…
Human Cyborg Relations
  • 189
1
vote
1 answer

if $f \sim g$ is $\text{Im}(f) \sim \text{Im}(g)$?

if $f \sim g$ is $\text{Im}(f) \sim \text{Im}(g)$? I wanted to find an asymptotic expansion to $\int_0^\infty e^{-xt} \sin(t) dt$ as $x \to \infty$ My thought was to look at $\int_0^\infty e^{-xt}e^{it}dt$ and then apply Watson's Lemma to show…
infinitylord
  • 4,777
1
vote
0 answers

Asymptotics / litte-o-notation

Why is the following true? \begin{equation} (1+o(1))n^{r+2}2^{-r}+n_{(r+1)}-n_{(r)}2^{r}(n-r)^{2}2^{-2r}=o(n^{r+2}), \end{equation} where $n_{(r)}=n(n-1) \cdots (n-r+1)$. In my opinion, the result should be $o(n^{r+3})$.
koala
  • 71
1
vote
0 answers

Asymptotic Bound for Iterated functions [Solved]

This is the definition from Introduction to Algorithms (3rd edition) Chapter 3, page 63 For any monotonically increasing function $f(n)$ over the reals, for a given constant $c \in \mathbb{R}$, we define the iterated function $f_{c}^{\ast}(n)$ by…
abs
  • 11
1
vote
0 answers

what is $\sum_{p\leq x}{p \log p}$ is equal to

This might be a simple question. But Can any one give me an asymptotic bound for $\sum_{p \leq x}{p \log p}$, where $p$ is a prime number
Math123
  • 1,243
1 2 3
…
74 75