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
4
votes
3 answers

Is $n^{0.01}$ Big Omega or Big O of $\log(n)$

I was graphing $n^{0.01}$ for huge values of $n$ and noticed this function grows incredibly slow, much slower then $\log(n)$ it appeared from the graph. So my initial thought was that $$n^{0.01}\in\mathcal O(\log(n))$$ $$\log^x(n)\in \mathcal…
T-bone's House
  • 63
  • 2
  • 8
4
votes
1 answer

Master Theorem when B is a fraction.

So I'm working through my homework, and applying the Master Theorem pretty easily, then my prof throws me a curve ball $T(n) = 4T(3n/4) + n^4$ Now I used my usual steps of listing out what A, B, and f(n) is: a = 4 b = 3/4 $f(n) = n^4$ but…
Wusiji
  • 141
4
votes
1 answer

If $f(n)\in O(g(n))$ can $g(n)\in O(f(n))$?

This may be a dumb question, but if $f(n)\in O(g(n))$ can $g(n)\in O(f(n))$? I can think of a few counter examples, like $n\in O(n^2)$ and obviously $n^2\notin O(n)$, but one counter example doesn't deny the existence of one case where it is true.…
roboguy12
  • 581
  • 2
  • 7
  • 18
4
votes
2 answers

Is it true that $ f(n) = O(g(n))$ implies $g(n) = O(f(n))$

So I have this is an assignment for algorithms. I've googled a lot, read the chapter in the book about big Oh notation, and I understand the concept. I do not however understand how to prove it. I know I need to work with a constant and put that out…
NicklasN
  • 141
4
votes
2 answers

Asymptotics of the sum $1-2^x+3^x-4^x+\cdots+x^x$

What is the asymptotics of $1-2^x+3^x-4^x+\cdots+x^x$ as $x$ becomes big? $x$ is odd only
Sigma4
  • 197
4
votes
3 answers

Why does $\log(n!)$ and $\log(n^n)$ have the same big-O complexity?

In an example that I found, it is said that $\log(n!)$ has the same big-O complexity as $\log(n^n)$. Please explain why this is the case.
Julia
  • 496
4
votes
1 answer

An asymptotic expansion for $(1 + \frac{x}{n})^n$.

I am trying to work out an asymptotic expansion for the function $$f(x, n) = \left(1 + \frac{x}{n}\right)^n$$ in the following sense. For all $k \geq 1$, let $f_k(x)$ be the function recursively defined by $$f_k(x) = \lim_{n\to\infty} n^k…
muaddib
  • 8,267
4
votes
2 answers

Asymptotic Behaviour Of $\frac{1}{x-1}+\frac{1}{x^2-1}+\frac{1}{x^3-1} + \cdots$ as $x \to 1 $

I define $$ f(x) = \sum_{n=1}^{\infty} \frac{1}{x^n-1} = \frac{1}{x-1} + \frac{1}{x^2-1} + \frac{1}{x^3-1} +\frac{1}{x^4-1} + \frac{1}{x^5-1} + \cdots$$ and I then wish to study the asymptotic behaviour of $f(x)$ as $x$ approaches 1. I have some…
Asier Calbet
  • 2,480
4
votes
2 answers

Difficulty proving a function exists in both Big $O$and Big $\Omega$

For an algorithm analysis homework assignment, I've been asked to show that $$f(n) = n{^2} + 3n{^3} \in \Theta(n{^3})$$ This means that its necessary to use the definitions of $O$ and $\Omega$ to prove that $f(n)$ is in both $O(n{^3})$ and…
Jason
  • 1,191
3
votes
1 answer

Heat Invariants on a one - dimensional Riemannian manifold

I am trying to understand the asymptotic heat trace expansion \begin{equation} \text{Tr}(e^{-t\triangle_g}) \backsim \sum_{k \geq 0} t^{k - \frac{n}{2}}c_{2k} \quad (t \to 0^+) \end{equation} that is associated with the Laplace - Beltrami…
harlekin
  • 8,740
3
votes
2 answers

is there a pair of functions that meets the next requirement?

How i can find a pair of functions that meets the next requirement $f,g: \mathbb{N} \rightarrow \mathbb{R^+_0}$ And that $f(n) \not \in O(g(n))$ and $g(n) \not \in O(f(n))$ also these functions must be increasing functions. My hunch is that there…
alan smith
  • 33
3
votes
1 answer

Understanding big $O$ notation.

This was a question on one of my previous exams. Sadly the solutions that were offered in class were torn off and lost at some point over the semester. Could someone guide me through the solutions to this? I'm strictly doing this for review. I…
user17366
3
votes
1 answer

Question on nested Big-O asymptotic notation

Assume you are given $f(x) \in O(n2^{O((\log \log n)^2)})$. My first question is what the exact definition of big-O is in case of nested functions. I have come up with the following: $\exists c > 0, \exists n_0 > 0, \forall n > n_0 \colon f(x) \leq…
Omega
  • 43
3
votes
2 answers

Showing $\log \frac{x^x}{x!}=O(x)$

I need to finish off a problem by showing that $\log (x^x/x!)=O(x)$. My first thought (after looking at a plot) was, "hah! this is easy...", but it appears I am unable to prove this. What I've got so far (and this might very well be in the wrong…
Carolus
  • 3,279
3
votes
1 answer

Proving that, if a function f is O(g), the ceiling of f is also O(g).

I'm having a bit of trouble with this problem: $$\forall (f, g) \in F, f \in O(g) \implies \lceil{f}\rceil \in O(g)$$ Where F is the family of functions from $\mathbb{N}$ to $\mathbb{R}^+$. I know that $f(n) \leq \lceil{f(n)}\rceil \leq f(n)+1$,…
user157000
  • 265
  • 2
  • 8
1 2 3
…
74 75