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
0 answers

Is the term with the largest growth rate always the most simple g(x) in Big O/Theta/Omega Notation?

I made a statement in my coursework that the term with the largest growth rate for an arbitrary function f(x) is always the most simple g(x) in Big O/Theta/Omega Notation (removing coefficients). I believe this to be true, but I'd like more…
Alex Hira
  • 49
0
votes
0 answers

diagonal asymptotes of a hyperbola

How do I calculate the asymptotes of the hyperbola $$y=\frac{2x(x+2)}{x-3} $$ I know the horizontal asymptotes, but the problem is what is the diagonal asymptote?
HypnoticBuggyWraithVirileBevy
  • 172
0
votes
1 answer

Master method to find the tight asymptotic bound

Master method usually deals with the equation having the following form : $$T (n) = aT (n/b) + f(n)$$ But what if my equation is like this? $$T( n) = T(5n/7) + n $$ How can I find the tight asymptotic bound for such equations? The n inside the T…
Simran Munot
  • 1
0
votes
0 answers

Big-O: If ${f(n)}=O(g(n))$, prove/disprove ${(f(n))^3} = O (g(n))^3 )$

I have to prove or disprove this: If ${f(n)}=O(g(n))$, prove/disprove ${(f(n))^3} = O (g(n))^3 )$. From what we are given: ${f(n)}<=C_1g(n)$ for some constant $C_1$. Now I have to show that ${(f(n))^3} <= C_2(g(n))^3 )$. My intuition says that we…
aky
  • 23
  • 3
0
votes
1 answer

Does x*sin(x) = θ(x) as x approaches infinity?

I'm trying to determine whether or not xsinx is both O(x) and Ω(x) as x approaches infinity. I know if it fulfills both conditions, it's the same as saying that xsinx = θx, and I'm pretty sure xsinx = O(x), because just looking at them on a graph,…
Mae Rinn
  • 11
  • 1
0
votes
2 answers

Calculate asymptotic upper bound for a function

consider the following function $f(n) =$ $n^{4.5}-$$(n-2)^{4.5}$ I want to calculate a good tighter upper bound for it. I calculated a lower bound for it like - $n^{4.5} - (n-2)^{4.5} >= n^{4.5} - \sqrt n * (n-2)^3$ Now if we expand $(n-2)^3$ the…
rohit sharma
  • 11
0
votes
2 answers

Asymptotics of $y = b + \frac{a}{f(x)}$

We are taught at school that every time we have a function like that: $y = b + \frac{a}{f(x)}$ Then, one of the asymptotes will be y = b For example: $y = (x + 1) + \frac{4}{x - 2}$ Then, the asymptotes will be: $y = (x + 1)$ $x = 2$ I wonder why…
Matheus Minguini
  • 159
0
votes
2 answers

What should be the value of the two constants C and N to prove this?

I am supposed to prove the following: $n^{10} = O(2^{n/2}) $ So I proceed as follows: There are $C > 0$ and $N \in \mathbb{N}$ such as for any $n \geqslant N$, $$n^{10} \leqslant C 2^{n/2}$$ $\iff$ $\frac{n^{10}}{2^{n/2}} \leqslant C$ But then I am…
roger_godement
  • 41
0
votes
1 answer

How to correctly compate $f(n)$ and $g(n)$ when working through $O(n)$ notation?

Going through theory, missing the idea, need a bit of help. So, the initial state is: $$f(n) = O(g(n))$$ Assume that $f$ and $g$ are both nondecreasing and always bigger than 1. And, from my understanding, $f$ must be less or equal to $g$, because…
sortas
  • 113
0
votes
1 answer

Double sum that grows at sublinear rate

Is there an example of a non-zero function $f: \mathbb{N} \to \mathbb{R}^+$ such that for any $n \in \mathbb{N}$, the following term is sublinear (or $o(n)$)? $$\sum_{j=1}^n \sum_{i=1}^j f(i)$$
user3294195
  • 479
0
votes
1 answer

Does $i(n) < \log (n)$ imply $\frac{\log i(n)}{n} \in o \left( \frac{\log n}{n} \right)$?

$i(n)$ is a sequence of nonnegative numbers (integers) indexed by $n$. I think it only implies $ ... \in O\left(\frac{\log n}{n} \right)$, yet the other assertion was made in some paper I am reading. Just wanted to confirm. Here's the relevant…
rims
  • 2,657
0
votes
2 answers

How to prove $n^{\log n}$ is $\mathcal{O}(2^n)$?

I've seen proofs here that help with $n\log n = \mathcal{O}(n^2)$. However, if we take it a step further, how could one prove $n^{\log n}$ is $ \mathcal{O}(2^n)$? We are assuming $n\in\mathbb{N}$. Would it extend to $n\in (0,\infty)$? If we apply…
shiv
  • 5
0
votes
1 answer

Big $O$ -- $k^n$ vs $(k-1)^n\cdot n$, $(k>1)$

I tried to do the following: $$ k^n = (k-1)^n\cdot \left(\frac{k}{k-1}\right)^{n}$$ Now if i compare the above expression on the R.H.S with $$(k-1)^n \cdot n$$ I just need to compare $n$ and $\left(\frac{k}{k-1}\right)^{n}$. Now $\frac{k}{k-1}$ will…
Kakarot_7
  • 151
0
votes
1 answer

Big O Notation in two equations

If $a = b + O (c)$, $d = e + O (f)$ and $b > e$, can we say that $a > d$? I proceeded by substracting the two equations. I think I have not done any thing wrong. It gives $a-d=b-e + O(c-f)$ and I am stuck here.Also c>f.
user58491
  • 134
0
votes
2 answers

If both $t_1(n)$ and $t_2(n)$ are $O(f(n))$, then what is $O(t_1(n) / t_2(n))$?

If both $t_1(n)$ and $t_2(n)$ are $O(f(n))$, then what is $O(t_1(n) / t_2(n))$? Here is my reasoning... I know that the following property holds: $$t_1(n)\cdot t_2(n) = O(f(n) \cdot f(n)) = O(f(n)^2) $$ But the inverse property does not…
user1534664
  • 1,272
1 2 3
…
74 75