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

how many ways to make change, asymptotics

This is a simplified coin-changing question. Suppose the only coins available are all powers of $10$ dollars. How many ways are there to make change for $\$ 1000000$? In general, to make change for any amount \$$N$, the answer is $C(N)$, where…
Empy2
  • 50,853
1
vote
2 answers

Understanding big O notation simplified function

Recently been looking into algorithms and trying to understand the big O notation. On the wikipedia website it gives an example linked below to image in reference. I'm struggling to understand why we can simplify the $-2x^3$ to $+2x^3$, and then on…
cookies
  • 13
1
vote
1 answer

$o\left(x^{1+\varepsilon}\right)$ for all $\varepsilon>0$ implies $O(x)$?

Suppose that I have shown a function $f$ is $o\left(x^{1-\varepsilon}\right)$ for all $\varepsilon>0$. Can I conclude that $f$ is $O(x)$? This seems intuitively right, but I can't seem to furnish a formal proof. EDIT: The above should read…
funklejo
  • 13
1
vote
0 answers

Is it $x-[x]-\frac{1}{2}$ or $x-[x]+1$ in the derivation of the Euler Summation formula

The theorem on the Euler Maclaurin Summation formula usually involves the term $x-\lfloor x\rfloor-\frac{1}{2}$, however in some other text, I sometimes also see the term $x-\lfloor x\rfloor+1$ instead. I came across this issue after looking at…
Seth
  • 3,325
1
vote
1 answer

Is $\log_2(2^{k^2-k}-(2^{k-1}-1)^k) = k^2-2k+o(k)$?

I am trying to show that $\log_2(2^{k^2-k}-(2^{k-1}-1)^k) = k^2-2k+o(k)$. This question is coming from this paper. On page 5 of the paper, after Conjecture 3.1, the authors discuss an example. I have computed the cardinality of that family $\mathcal…
alephnot
  • 300
1
vote
0 answers

Asymptotic growth of recursively defined series

Assuming I have a series $a^m(k)$ defined as follows (m being a superscript - not an exponent): $$ a^m(k) = a_k^{m} = \sum_{i=1}^{k} \, a_{i-1}^{m-1}\\ ...\\ a_k^{2} = \sum_{i=1}^{k} a_{i-1}^{1} \\ a_k^{1} = 1 \\ \text{and}\\ a_0^{1} = 1, ~a_0^{m}…
MikeMB
  • 133
1
vote
2 answers

How quickly does $y_{n+1}=y_n(1-1/\lg y_n)$ decrease?

The iterated logarithm $\log^*(x)$ is defined to be the smallest $n$ such that $\log^{(n)}(x)\le 1$. Similarly, let's define $f^*(x)$ to be the smallest $n$ such that $f^{(n)}(x)\le 10$, where $f(x)=x\cdot(1-1/\lg x)$. We can show that…
rgrig
  • 1,002
1
vote
1 answer

Big Theta $\sum_{i=1}^n i^2\ln(e+\frac{1}{i})=\Theta(n^3)$

Please help explain $\sum_{i=1}^n i^2\ln(e+\frac{1}{i})=\Theta(n^3)$. I intuitively get it, but would appreciate if someone could actually provide a rigorous approach.
Samantha
  • 23
  • 2
1
vote
1 answer

Simplify fractions with Big-$O$ in the denominator

This question might be very simple, but I'm having a hard time understanding it. Suppose $$f(n) = \frac{O(n)}{1+O(1/n^2)}.$$ How can I "simplify" the fraction so that I get $f(n) = O($something$)$? I think it should be $f(n) = O(n)$ ... My…
Babado
  • 1,306
1
vote
2 answers

Which grows faster $n^{\log(\log n)}$ or $(\log n)^{\log n}$

I usually just try playing around with properties of log, but it doesn't help in this case.
Alzebrian
  • 61
  • 5
1
vote
2 answers

Does $f(\epsilon)=o(\epsilon\ln(\epsilon))$ imply $\frac{f(\epsilon)}{\epsilon}=o(1)$?

I have the following homework question: Does $f(\epsilon)=o(\epsilon\ln(\epsilon))$ imply $\frac{f(\epsilon)}{\epsilon}=o(1)$ ? It doesn't seem correct to me, using the definition I could only…
Belgi
  • 23,150
1
vote
1 answer

How do you prove that if $f(n)\in O(g(n))$ then $g(n)\in\Omega(f(n))$

Prove that if $f(n)\in O(g(n))$ then $g(n)\in\Omega(f(n))$ I saw a proof of this from the site from way back. I am not convinced this is true with the statement THEN between. This is Transpose symmetry I think and the statement in between Prove…
david
  • 9
1
vote
2 answers

Is $x2^x = O(2^x)$?

Is $x2^x = O(2^x)$? Intuitively it seems like the answer is no. But if we write $x2^x=2^{\log x + x}$ then the answer (to me) is unclear. Thanks in advance!
lollab
  • 73
1
vote
1 answer

"$f(x)$ decays AT LEAST as $1/x$: Is this Big-Oh notation or Little-oh notation rather?

If I want to show that, as $x\to x_0$, the function $f(x)$ decreases to some value at least as fast as $1/x$, is this saying that one wants to show that $f(x)\in O(1/x)$ as $x\to x_0$? Or does the "at least" rather mean the little-oh idea, i.e.…
Salamo
  • 1,094
1
vote
1 answer

Does being asymptotic imply the use of Big-O notation and vice-versa?

Suppose that $f(x)\sim g(x)$, then does $f(x)=O(g(x))$? Conversely, suppose that $f(x)=O(g(x))$, then does $f(x)\sim g(x)$?
lilliege
  • 65
1 2 3
…
74 75