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

Orders of growth of typical sequences

It's been a while since I had to deal with some sort of asymptotic analysis so I am a bit rusty and trying to get the basics back together. Since I don't really know where to look for these things, I ask you: is the following correct? Let $p_i,q_i…
user46225
  • 731
  • 4
  • 11
0
votes
1 answer

Big O Notation Arithmetics

Assuming it is known that: $$ t\sqrt n = O((nt)^{2/3}+n+t)$$ How is it possible to deduce a bound on $ t $? Specifically, I need to prove that $ t = O(\sqrt n)$. This is part of a bigger question, so I am not sure the above formula is correct. I…
Artium
  • 950
0
votes
1 answer

Lower bounds for an expression of two positive integers?

Can we get an approximate lower bounds for the following expression: $$\left( 1 + \frac{1}{ 2 \left( \frac{4^{nC}-1}{2^n-1} \right) } \right)^{ \frac{1}{\left( \frac{4^{nC}-2^{nC}}{2^n-1} \right) } } -1$$ ...where $n$ and $C$ are positive integers…
Matt Groff
  • 6,117
-1
votes
1 answer

Prove $\left\lfloor n\right\rfloor = n + O(1)$

Can someone show me why $\left\lfloor n\right\rfloor = n + O(1)$. Using the same logic, can anyone derive a similar proposition for $\left\lceil n\right\rceil$?
Olórin
  • 5,415
-1
votes
2 answers

Two questions in asymptotic notation

I have to prove two equations and I can't understand them. Any help would be grateful because I have to consign the whole project in two days. These are the equations: If $f(n)=O(g(n))$ and $z(n)=O(h(n))$, then $f(n)+z(n)=O(g(n)+h(n))$. I have to…
Dominus_Mors
  • 11
-1
votes
1 answer

asymptotic notations and their running time

I know that for $f(x) = O(g(x))$ running time $T(n) = O(n^3)$ $f(x) = \Omega(g(x))$ running time $T(n) = \Omega(n^2)$ but what is the $T(n)$ for $f(x) = Θ(g(x))$ ? Also tell me running time for little-oh (o) & little-omega (\omega) Also what is…
Abhimanyu Aryan
  • 55
  • 4
-1
votes
1 answer

Prove that |O(2n)-O(n)|=O(n)

I need to prove that statement with the defenition of big O |O(2n)-O(n)|=O(n) Does it can be proven? or not? if i can, so how..in which way? i tried almost everything
pili66
  • 1
-1
votes
1 answer

Big O Notation for a constant running time

I came across a question asking the following: Why is the O-notation for a constant running time always given as O(1)? I have been thinking about it but I can't make sense of it. Could anyone shed any light on the question at hand?
C_B
  • 111
-1
votes
2 answers

Prove that $f(n)=n^2+2^n$ is $\cal{O}(g(n))$, where $g(n)=3^n$

Prove that $f(n)$ is $\cal{O}(g(n))$, where $$f(n)=n^2+2^n$$ $$g(n)=3^n$$ I tried finding the limit using l'Hôpital's rule and breaking it into parts but it got too complicated.
user42282
-1
votes
1 answer

Finding $k$, $C_1$, and $C_2$ when $f(x)$ is $Θ(g(x))$

How can I find the constants $k$, $C_1$, and $C_2$ when I know that $f(x)$ is $Θ(g(x))$? $f(x)=3x^2+x+1$ and $g(x)=3x^2$ I have that $C_1g(x) \le f(x) \le C_2g(x)$ $C_1 \le \frac{f(x)}{g(x)} \le C_2$, but where do I go from here?
Simen
  • 13
-1
votes
1 answer

Prove if $f(x) = 4x^2 +9$, $f(x) = \Omega (x \log x)$

How do I prove this using inequalities? I know that since $4x^2 +9= \Omega (x^2)$, it follows that $4x^2 +9$ is $\Omega (x \log x)$ since Big Omega is a lower bound. But how do I prove it using inequalities and choose a $n_0$ and c? I don't really…
anoushka
  • 7
-1
votes
1 answer

Comparing $x\log x^2$ and $(\log x)^{2\log x}$.

I have this question in a past worksheet that asks me to order 2 functions by order of growth: $$f_{1}(x) = x\log(x^{2})\\ f_{2}(x) = (\log (x))^{2\log(x))} $$ I had seen in desmos the $f_{2}(x)$ is greater, but I'm not sure how to prove this,…
user438409385
  • 11
-1
votes
1 answer

for $f(n) = (3n-7)/(n+4)$ and $g(n) = 4$, is g = O(f)?

I am stuck on this problem. $f(n) = \frac {3n-7}{n+4}$ and $g(n) = 4$, is $g = O(f)$? when I take the $\lim_{n\to\infty} {g(n) \over f(n)}$, then it's a constant ${4 \over 3}$ which is less then infinity and satisfies the definition of $g =…
Jay
  • 9
-1
votes
1 answer

Proving $n^3 \in \omega(n^2 (\log n)^2)$

I have $$n^3 > M n^2(\log n)^2$$ $$n > M (\log n)^2$$ (Since $\log n < n$.) $$n > M (n)^2$$ $$1/n > M$$ $$1/M > n$$ Therefore define n0 to be any value less than $1/M$. But plotting the graph on Desmos does not seem correct. I think I may have gone…
Boris
  • 9
-1
votes
2 answers

Big Omega of a Summation: $\sum_{k=1}^n\sqrt{k\log k}=\Omega\left(\sqrt{n^3\log n}\right)$

I can solve the upper bound of the following series but stuck in prove this: $$\sum_{k=1}^n\sqrt{k\log k}=\Omega\left(\sqrt{n^3\log n}\right)$$ Update: Thanks all, I was looking for a simple discrete proof like this: $$ \exists c>0,n_0>0,\;\forall…
Sam
  • 1
1 2 3
…
74 75