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

If there exists $c$ and $k$ such that $f(n) = c \cdot g(n)$, is $f(n)$ big theta?

I'm doing some reading up on Big O, Omega and Theta. From what I understand if $f(n)$ is Big O ($f(n) \leq c\cdot g(n)$) and $f(n)$ is Big Omega ($f(n) \geq c\cdot g(n)$), then $f(n)$ is Big Theta. If I'm able to find a constant $c$ and $n$ such…
Extreme112
  • 253
0
votes
1 answer

How to extract constants for proving $f(n) = \Omega(g(n))$

I need to prove or disprove $n\log_2(n)-3n-18 = \Omega(n)$ and get appropriate constants so that the lower bound limit definition is fulfilled. My attempt In order to prove that relation, I use the notion of limit: $$\lim_{n \to \infty}…
haunted85
  • 1,418
0
votes
0 answers

How do I prove tight bound

I have a recurrence relation: T(n)= 3T(n-1)-2T(n-2) Where n>1 . note when 1, n=1. and when 0, n=0 . Find a tight bound for T(n). How do I now prove that it's big O and Ω in order to prove it's tight bound Not really sure how to solve this. Any…
Hani
  • 11
0
votes
4 answers

Prove $\frac{n^2+1}{n+1}$ is $\mathcal{O}(n)$

I'm trying to proving this formula $\frac{n^2+1}{n+1}$ is $\mathcal{O}(n)$. As you know we need to come up with $n_0$ and $C$. So I'm confusing a little bit in how to choose a appropriate $C$ since the equation here is division. For $n > 1$,…
Hani
  • 11
0
votes
0 answers

Asymptotic Notation for factorial functions

Indicate whether or not each function below is $( \log ())$: 1) $\dfrac{5^2}{\log(n)^3}$ 2)$\log((^2)!)$ I am stuck when I try to simplify these functions and find their growth rates.
Rijul
  • 1
0
votes
1 answer

What's the asymptotic relation of $\log^{2}n$ and $\sqrt{n}$?

I tried differentiate the two functions, then I got $\frac{2\log n}{n}$ and $\frac{1}{2\sqrt{n}}$. Take the limit on the ratio, we can get $\lim_{n \rightarrow \infty} \frac{2logn/n}{1/2\sqrt{n}} $ Then substitute n by $m^2$, $\lim_{n \rightarrow…
Jasw1ne
  • 1
0
votes
0 answers

Meaning of "$\omega (n) \rightarrow \infty$ arbitrarily slowly"

I am studying Turan's proof of the fact that "almost all" $n$ have "very close to" $\ln \ln n$ prime factors. The statement of the theorem is: Let $\omega (n) \rightarrow \infty$ arbitrarily slowly. Then the number of $x$ in $\{1, 2, ..., n \}$ such…
JDF
  • 878
0
votes
2 answers

Dealing with big O

Is this true or false? $(n(n+1)(n+2))/6$ is $O(n^3)$ (big O) I have broken it down to this $(n^3 + 3n^2 + 2n) / 6$ but am unsure what to do next to prove/disprove this statement.
Racehorse35
  • 21
0
votes
2 answers

Asymptotic notation_problem

Consider a Function f(n) and g(n),now my question is that is it possible that f(n) is a member of bigOh(g(n)) as well as a member of smalloh(g(n)). I am confused because of this question's solution http://clrs.skanev.com/03/problems/02.html how can…
sourav_anand
  • 551
0
votes
1 answer

Prove that $15n \log(5n) = \Theta(n \log(n))$

I must determine the positive constants $c_1$, $c_2$, and $n_0$ such that $$c_1 n \log(n) \leq 15n \log(5n) \leq c_2 n \log(n)$$ To simplify I attempted to divide by $$n \log(n))$$ however this yielded a messy result involving changing the base of…
Clark Bell
  • 25
0
votes
1 answer

If $g(n_0)\le cf(n_0)$ for some $(n_0,c)$ then $g(n)\le cf(n)$ for every $n>n_0$, or not?

I'm currently studying Algorithms Design and Analysis and our teacher today started talking about Asymptotic Analysis. He said that, after choosing an arbitrary $c$, if you manage to find a $n_0$ that satisfies $f(n_0) \ge c*g(n)$, that in turn…
andre_ss6
  • 101
0
votes
1 answer

Why does $f_{1}(n) = 10n^3 + 5n^2 + 17 \in \theta(n^3)$?

I saw this in this lecture : Asymptotic Notation at the 15 minute mark. But I don't understand it. And also why does $f_{2}(n) = 2n^3 + 3n + 79 \in\theta(n^3)$? I don't understand the proof.
jimpix
  • 211
0
votes
0 answers

Prove $f_1(n) * f_2(n) = O (g_1(n)*g_2(n))$

Prove $$f_1(n) * f_2(n) = O (g_1(n)*g_2(n))$$ Given: $f_1(n) = O(g_1(n)) , f_2(n) = O(g_2(n))$ So I started by saying: $\exists n_0,c_1 , \forall n \gt n_0 : f_1(n) \le c_1\cdot g1(n)$ $\exists n_1,c_2 , \forall n \gt n_1 :f_2(n) \le c_2\cdot…
Ilan Aizelman WS
  • 4,128
0
votes
4 answers

prove $n$ is $O(n\log n)$

In order to prove that $n$ is $O(n\log n)$, as per my understanding if we have to say $f(n)$ is $O(g(n))$ then $\lim\limits_{n \to \infty} \frac{f(n)}{g(n)}= C$ Then in that case when I am taking the limit $\lim\limits_{n\to\infty} \frac{n}{n\log…
Siddarth
  • 133
0
votes
1 answer

true or false : is $2^n = Ω(3^n) $

$2^n = Ω(3^n) $ let $n= 0$ then $1<1*c$ for any $c>1$ so my answer is yes, but the textbook answer implies I am wrong. may I know where I am doing it wrongly?
user360110
  • 1
1 2 3
…
74 75