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

What is the relative time complexity for f(n) = loglog(n), g(n) = log(n)

I know the answer is f(n) is Big O of g(n). This is the graph for f(n) and g(n). Here when C is 1, this is the case and f(n) is upper bounded by g(n). When I'm giving 0.1 as the C value, as shown below, we see that for sufficiently large values of…
Jake
  • 21
-1
votes
2 answers

Big O problem $2^n$ and $n^2$

How can i prove that $$2^n\not \in O(n^2)$$ by formal definition and not using limits? With:
Vicente Merino
  • 57
-1
votes
1 answer

order of $ln(1+\epsilon)$ as $\epsilon \rightarrow 0$

I am struggling with understanding how to find the order of this expression. The answer in the solutions is $\lim_{\epsilon \to 0}= \frac{ln(1+\epsilon)}{\epsilon}$. I don't understand the concept of putting $\epsilon$ in the denominator
user643396
  • 3
-1
votes
1 answer

Ordering w.r.t increase in growth rate

What is the growth rate and how can we order given functions w.r.t increase in growth rate? How can we order the following functions ascending with respective to the rate of growth:…
Sail Akhil
  • 29
  • 5
-1
votes
1 answer

How can I prove $20n = O(n^6)$

I am trying to understand how to prove or disprove this: $$20n = O(n^6) $$ I think it is false, but I am lost on how to show it.
J_Strauton
  • 109
-1
votes
1 answer

Proof of Big O notation example

I am a beginner and taking an online algorithm course, and when I referred to a book, I found the following question. Given that $f(x) = 2x^2 + 5x +3$ and $g(x) = 2x^3 +x -100$, prove $f(x) = O(g(x))$ I know that to prove $f(x) = O(g(x))$, I have…
Jonatan
  • 13
-1
votes
1 answer

Prove or disprove the following claim for all monotonically increasing functions $f(n)$

Prove or disprove the following claim for all monotonically increasing functions $f(n)$. $$f(n) = \theta ((f(\sqrt{n}))^2)$$
Priya Singh
  • 1
-1
votes
1 answer

Subtraction with Big O notation

How does the sustraction works for big O notation? I have to functions, lets say $f(x)=p(x)+O(\ln(r(x)))$ and $g(x)=q(x)+O(\ln(s(x)))$ and I want to consider $f(x)-g(x)$ there is a way to simplify $O(\ln(r(x)))-O(\ln(s(x)))$? What this even…
Luis GC
  • 412
-1
votes
2 answers

Is $3^{(2n)} = O(3^n)$ ? Why?

Working on a Computer Science Fundamentals assignment and came across this. I see that I am supposed to find a $C$ for something... but that is about all i know. Can anyone break this down for me? Thanks in advance.
djjeane
  • 1
-1
votes
1 answer

Does ${O}2^n$ grow faster or slower than ${O}3^{(n/2)}$?

Is $\mathcal{O}(3^{n/2})$ equal to $\mathcal{O}(3^n)$? I am not sure how the growth of exponentials with fractions.
LuxuryWaffles
  • 105
  • 1
  • 5
-1
votes
1 answer

Proving that $f(n) = o(g(n)) => 2^{f(n)} = O(2^{g(n)})$

I can't find a counter example to this formula, or in case if its true - what is the correct way to prove it... In this case, first o is "little-o notation" - a strict upper bound. And second is "big-O notation". I found here fine examples, that…
Jaroslav
  • 9
-1
votes
2 answers

How do I find the simplest Big O estimate for this function?

$$r(n) = \Big(\sqrt{n}+20\log_2(n)+n/2\Big)\big(4n+\log(n)+5\big)$$ This was part of my computing science quiz, and I still can't happen to understand how to find the simplest big O estimate. It would be greatly appreciated if someone could help me…
stanley cho
  • 99
-1
votes
2 answers

Big O, Omega and Theta Notation

For time complexity I get that: O(n) = worst case $\Omega$(n) = best case $\Theta$(n) = exactly (best and worse) But I'm facing the following: "State weather the statement is true or false. If true, provide justification, and if false, give the…
OrdinaryHuman
  • 219
-1
votes
1 answer

Asymptotic Notation Implications

Do the following implications hold, I can see that the reverse implication will be true and these implications seem to be true as well, but I can't think of a way to prove or disprove it. Can anyone think of a counter example?
Ioyo
  • 3
  • 1
-1
votes
1 answer

Simple Big Theta, $\Theta$, notation definition

Could it be said that: $f(x) = \Theta (g(x))$ if, for some large $x$, the functions $f(x)$ and $g(x)$ differ only by a constant scale factor, i.e. either $f(x) = \frac{g(x)}{C}$ or $f(x) = Cg(x)$, where $C = const$. ? Could you help me…
Ziezi
  • 631
1 2 3
…
74 75