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
0
votes
1 answer

Finding the asymptotics of a summation

Let $n\in\mathbb{Z}^+$ and $T_n = 1\sqrt{1} + 2\sqrt{2} +\cdots+ n\sqrt{n}$. Finding $\mathcal{O}(T_n)$, $\mathcal{\Omega}(T_n)$ and $\mathcal{\Theta}(T_n)$
qwerty89
  • 726
0
votes
1 answer

Is This Statement True?

Is it correct to assert that $T(n) \in \Theta(n^2)$ when: $$ \frac{n^2}{\log{(n)}} \leq T(n) \leq \frac{n^2}{\log{(n)}} + n $$
Mohamed Ennahdi El Idrissi
  • 315
0
votes
1 answer

General questions concerning asymptotic behavior

I have some difficulties understanding asymptotics in general. Is $O(n)$ the same as $O(-n)$? Is $O(f(n))$ the same as $O(cf(n))$ even though we know that $f(n)\leq 1$ for all $n$? I know the general Standard rules you can find e.g. on Wikipedia,…
user146358
  • 309
0
votes
1 answer

Is this Asymptotic Statement true?

Is this statement true? If so, how can I prove it? If not, why not? $$ \frac{n^2}{\log{(n)}} \in \Theta(n^2) $$ Recall the definition of Big Theta asymptotic notation: $f(n) \in \Theta(g(n))$ means that there exist constants $k_1$ and $k_2$ such…
Mohamed Ennahdi El Idrissi
  • 315
0
votes
1 answer

If $f(n) = \Theta(g(n))$, then $cf(n) = \Theta(g(n))$ for any $c \neq 0$

How would I prove: If $f(n) = \Theta(g(n))$, then $cf(n) = \Theta (g(n))$ for any $c \neq 0$. I'm pretty sure it's true, but not sure how to prove it.
John M.
  • 71
0
votes
2 answers

Discrete Mathematics: Prove that f(x) is in O(x)

Prove that $$\frac{2x^{2}+x}{x+1}$$ is in $O(x)$
M.E.
  • 247
0
votes
1 answer

Interpreting expression with big-O notation in the exponent ($f(x) = x^{1+O(1)}$)

How should one interpret the notation $f(x) = x^{1+O(1)}$? I'm a bit confused as to what this means. Does it merely suggest that f(x) grows as some integer power of x?
Improve
  • 1,788
0
votes
2 answers

Big Omega -- n, n + 100

Given $f(n) = n$ and $g(n) = n + 100$, it seems that f(n) is $O(g(n))$ when $C = 1$ and $k= 0$. That is, for every $n$ from $0$ to infinity, g(n) is strictly larger than f(n). Now, concerning $\Omega$ notation, it seems that we could also say that…
compguy24
  • 421
0
votes
1 answer

Prove the following $\frac{\Omega(f(n))}{\Omega(g(n))} \subseteq \Omega(\frac{f(n)}{g(n)})$

I want to prove the following: $$\frac{\Omega(f(n))}{\Omega(g(n))} \subseteq \Omega(\frac{f(n)}{g(n)})$$ I wonder if its true? What about using $n$ and $n^2$? Any suggestions? Thanks!
Ofir Attia
  • 3,136
0
votes
2 answers

Asymptotics - Big Omega

I have a question about Asymptotics involving big Omega... How do I need to approach this equation in order to prove it? $$n \cdotΩ(f(n)) = Ω(n\cdot f(n))$$ Thank you very much for your answers!
Shar
  • 11
0
votes
1 answer

Prove $\Omega(f(n)) \subset \Omega(g(n)), iff : g(n)\in \mathcal{O}(f(n)) \wedge f(n) \not\in \mathcal{O}(g(n))$

I want to prove the following $$\Omega(f(n)) \subset \Omega(g(n)), iff : g(n)\in \mathcal{O}(f(n)) \wedge f(n) \not\in \mathcal{O}(g(n))$$ What I did so far is: $$t(n)\in\Omega(f(n)) \rightarrow \exists c_{1} \exists n_{0} \forall n>n_{0} ,…
Ofir Attia
  • 3,136
0
votes
2 answers

Is it true that $|O(2n) - O(n)|=O(n)$?

I need to prove or contradict:$$|O(2n) - O(n)|=O(n)$$ I try: $$\\f(n)=1.5n\in O(2n),g(n)=0.25n\in O(n),h(n)>0\in O(n) : \\ |1.5n - 0.25n|=h(n)\\1.h(n)=1.25n \in O(n)\\ but: 2. h(n)=-1.25n \notin O(n)$$ Is that true?
user2976686
  • 185
  • 8
0
votes
1 answer

Show that $f(n) = 2n^4 + 4n^2 + 5$ has a tight bound of $\Theta(n^4)$

What I have done so far (planning on showing lower and upper bound first): Lower bound: $$c_1n^4 \leq 2n^4 + 4n^2 + 5$$ Divide by $n^4$ $$c_1 \leq 2 + \frac{4}{n^2} + \frac{5}{n^4}$$ Take limit as n approaches infinity $$c_1 \leq 2 + 0 +…
kaozgamer
  • 3
0
votes
1 answer

$|f(n)-g(n)|\in \mathcal{O}(t(n)) $ And $f(n)+g(n)\in \Omega(t(n))$,Its true that $f(n)\in \Omega(t(n))$?

I want to prove the following by the definition $$|f(n)-g(n)|\in \mathcal{O}(t(n)) $$ $$f(n)+g(n)\in \Omega(t(n))$$ Is it true that $f(n)\in \Omega(t(n))$? What I tried is just think about functions, it seems true, but I don't know how to prove…
Ofir Attia
  • 3,136
0
votes
0 answers

How does one begin to find an asymptotic function of an infinite power series?

Say we have the infinite series $$\sum_{n=0}^\infty a_nx^n.$$ We want to attempt to find an asymptotic function/relation to the above series. How does one begin? I have never dealt with this area of math (undergraduate at the moment). Does one need…
H5159
  • 969
1 2 3
…
74 75