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

Strange big-O notation?

I recently stumbled upon some Landau notation I don't quite understand... It's the normal big-O notation with one or more indices, like: $$\log{\vert{L(s,\chi)}\vert}\le\mathcal{O}_\epsilon(\log{q(2+\vert{t}\vert)}$$ for some constants…
C. Brendel
  • 874
  • 6
  • 14
1
vote
2 answers

What does asymptotically proportional mean?

In an article about Metcalfe's law, I've read that $n(n-1)/2$ is asymptotically proportional to $n^2$. What does this mean? PS: I did find asymptotically optimal but I'm not sure if they mean the same thing.
Bob van Luijt
  • 111
1
vote
1 answer

Simplifying Equation - Asymptotic analysis

The textbook I'm using for the course Introduction to Algorithms class has the following statement in it: The equation of such a line is $\log (T(N)) = 3 \log N + \log a$ (where a is a constant) which is equivalent to $T(N) = a N^{3}$ My rusty…
e.inglewood
  • 13
1
vote
1 answer

$f(x)=O(x^2), x\to 0$, then $f(x)-x=O(x^2), x\to 0$?

Suppose $f(x)=O(x^2)$ as $x\to 0$, which means the big-Oh-notation. My question is whether then $$ f(x)-x=O(x^2)\text{ as }x\to 0. $$ On the one hand, my answer is yes since $g(x):=x=O(x)$ as $x\to 0$ and hence $f(x)$ is the dominant term in the sum…
Rhjg
  • 2,029
1
vote
1 answer

If not an upper bound, is it a lower bound?

I wanted some help with a bounding question. The question asks that if $f$ is not an upper bound on $g$, is it a lower bound? $f,g: \mathbb{N} \to \mathbb{N} \cup \{\infty\}$. By definition for an upper bound, there exists a constant $c$, there…
Joe Mann
  • 13
1
vote
2 answers

Sigma notation in regards to computer science time complexities

I have been attempting to solve this problem for a while now, but I am not sure how to truly start it. $\sum\limits_{i=1}^N (2i-1) = N^2 $ So far I have found that $\sum\limits_{i=1}^N (2i-1) = (2(1)-1) + (2(2)-1) .... (2(N)-1) $ But this does not…
kyle newton
  • 15
1
vote
2 answers

Does little-o notation imply going into infinity?

Let $f(n)=o(g(n))$. By definition there exists $n_0$ so that for all $n>n_0$ it holds that $\varepsilon \cdot g(n) \geq f(n)$ for $\varepsilon>0$ however small. So, in plain language, starting from a certain point, $g(n)$ grows significantly faster…
Ilya
  • 273
1
vote
2 answers

Asymptotic notations - Big Omega Proof

I had a question in my final exam in data structures, very confusing question, the following: Prove by the definition that: $15n^2+7n-6= \Omega (17n^2+5n-10)$. Let's denote: $f(n) = 15n^2+7n-6, g(n) = 17n^2+5n-10.$ From the begining, when i look at…
D.Rotnemer
  • 459
1
vote
1 answer

Why $\frac{1}{(4p)^a}\left(-\frac{a}{p}+\mathcal O\left(\frac{1}{p}\right)\right)\sim_{p\to \infty }\frac{-a}{4^\alpha p^{a+1}}$?

For $\alpha >0$, I have to show that $$\sum_{n=1}^\infty \frac{(-1)^{\frac{n(n+1)}{2}}}{n^\alpha }$$ is convergent. In my book, if $u_n=\frac{(-1)^{\frac{n(n+1)}{2}}}{n^\alpha }$, they set $$v_p=u_{4p}+u_{4p+1}+u_{4p+2}+u_{4p+3},$$ and they proved…
Peter
  • 1,005
1
vote
1 answer

Find an equivalent to $\sum_{k=n}^\infty \frac{1}{k!}$

I would like to find an equivalent of $\sum_{k=n}^\infty \frac{1}{k!}$. Can I do as follow ? (since I always have doubt with those $o$ and $O$, I would like your opinion. $$n!\sum_{k=n}^\infty…
Peter
  • 1,005
1
vote
2 answers

Big Theta equivalence classes and proofs

I have a series of equation and I need to find which are in the same big theta equivalence class and order them. I am super confused by big theta. The equations…
user48812
  • 43
1
vote
1 answer

Solving an asymptotic equivalence for x

This might be a very dumb question, but I have googled around and looked in asymptotic analysis reference texts and cannot seem to find what I am looking for. So here we go: Suppose I know that there exists some $x$ such that $xn \sim n^2$ as $n \to…
H. Löw
  • 161
1
vote
3 answers

An argument involving big-O notation

I came across the following argument in my discrete maths textbook: Since $n=O(n), 2n=O(n)$ etc., we have: $$ S(n)=\sum_{k=1}^nkn=\sum_{k=1}^nO(n)=O(n^2) $$ The accompanying question in the book is: What is wrong with the above argument? Attempt:…
A Slow Learner
  • 1,201
1
vote
2 answers

$T(n) \le cn\lg n-cn+n\le cn\log n$ for $c \geq 1$

I am confused with respect to this equality. For $c>=1$, $(n-cn)$ should be less and less. For example if $c = 2, then (n-cn)$ should be $-n$ and overall equality changes to $T(n)<= nlogn - n$. And thus $cn\log n-cn+n$ should decrease for larger…
trickster
  • 39
1
vote
1 answer

Let f(n)=(n^loga)(lgn^k); a>=1. Which of the following statements are true:

a) $f(n) = O(n^{\log a}-e)$ for some $e>0$ b) $f(n) = \Theta(n^{\log a})$ c) $f(n) = \Omega(n^{\log a}+e)$ for some $e>0$ I think the last is true since limit of $f(n)/g(n)$ is infinity. So $f(n)$ is little omega of $g(n)$. So an $e$ must exist for…
trickster
  • 39
1 2 3
…
74 75