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

$\ln(f(n))\in \theta(\ln(g(n)))$ Its true that: $(g(n))^{f(n)}\in \theta((f(n)^{g(n)})$?

I want to prove the following: $\ln(f(n))\in \theta(\ln(g(n)))$ It's true that: $$(g(n))^{f(n)}\in \theta((f(n)^{g(n)})$$ How I can use $\ln$ function to prove it? prove by definition is preferred? or with limit rule?
Ofir Attia
  • 3,136
1
vote
2 answers

Big O / Logarithmic Equivalency

In one of the algorithms textbooks I was reading, it states that $O(3^{\log_2n})$ can be rewritten as $O(n^{\log_23})$. Why is this the case?
Public Display Name
  • 233
1
vote
2 answers

Understanding big O notation examples

I understand the main idea of big-O-notation, yet I have two questions regarding to the following examples: Prove/Disprove: 1. $2^{2n+1} = O(2^{2n})$ 2. $2^n = O(2^{n\over 2})$ Questions: I looked at the proof showing that the expression…
AnnieOK
  • 2,920
1
vote
1 answer

Big O Notation Exercise

I'm having a small problem. I'm very new in this section so please bear with me. I understand Big O meaning what everything signifies like the $O(n), O(n^2), O(x^n), O(\log n)$ and $O(1)$. I also learn the very basic of $\Omega$ and $\Theta$. The…
Yann Bohbot
  • 13
1
vote
2 answers

Prove that $a^n$ is $O(n!)$.

I proved by induction that $2^n = O(n!)$. Can this fact be used to prove the following: Let $a$ be a positive constant and $n$ be a natural number. Show that $a^n=O(n!)$. I have already written a proof that $2^n
user10747
  • 117
1
vote
1 answer

Big-O: Prove that d^n = O(n!)

Suppose constant d>0. Prove d^n = O(n!) left to right prove only, is there any way to prove that other than using limit?
Lisa
  • 145
1
vote
0 answers

How does one prove that $n^{-100} = \omega(2^{\sqrt{\log{n}}})$?

I feel that $2^{\sqrt{\log{n}}}$ could be dramatically simplified, but I'm sure how. Aside from plugging in huge values to test the functions, any ideas on how I can prove this relationship?
David Faux
  • 3,425
1
vote
2 answers

Properties that hold when $f = \mathcal{O}(g)$

This is a homework problem. There are two questions where the answers seem intuitive, but even if I were correct in assuming they were true, I'd still need to provide a proof: When $f(n) = \mathcal{O}(g(n))$, do these two statements hold…
ಠ_ಠ
  • 143
1
vote
1 answer

Prove that $f(n)$ is in $\Theta(g(n))$

Suppose $f(n) = 1^k + 2^k + \ldots + n^k \;$ and $\; g(n) = n^{k+1}.\;$ Prove that $\;f(n)\in \Theta(n^{k+1})$. My understanding is that we have to find $C_1, C_2 \gt 0$ such that: $$C_1(n^{k+1})\le 1^k + 2^k + ... + n^k \le C_2(n^{k+1})$$ …
EggHead
  • 667
1
vote
1 answer

Big Omega for values going to zero

Usually, at least in Computer Science, $f(x) = \Omega(g(x))$ if $ \exists C > 0, \exists x_0 : \forall x \geq x_0 : f(x) \geq C g(x)$ i.e. for large values of x, $f(x)$ is at least as big as some constant times $g(x)$. But what if I have a function…
stefan
  • 1,030
1
vote
1 answer

Proving $\Omega$ Notation

Prove the following: $$ \frac{n^2}{4} \log ^2 \left(\frac{n}{4}\right) = \Omega \left(\frac{n^2}{2} \log ^2 \left(\frac{n}{2}\right)\right)$$ Whatever I try to do gets me nowhere, I tried multiplying both sides by $\dfrac{2}{n^2}$ and got to the…
Georgey
  • 1,589
  • 2
  • 25
  • 39
1
vote
1 answer

Prove that $\max(f(n),g(n)) = \Theta(f(n)+g(n))$

Possible Duplicate: how can be prove that $\max(f(n),g(n)) = \theta(f(n)+g(n))$ How to prove $max(f(n),g(n)) = Θ(f(n)+g(n))$?
Robert Badea
  • 396
1
vote
1 answer

Question about $\Theta$ notation

Are statements below true or false? $(1+1/n)^n = \Theta(\log n)$ $\log \log n = o(\log n)$ Note that it is little-o, not big-O For first statement, I thought it would have $\Theta(n^2)$ complexity so it is false, while the second statement is true.…
user482594
  • 127
1
vote
0 answers

Asymptotically evaluating integrals with oscillatory behaviour in both numerator and denominator

I have come across an integral that I would like to asymptotically evaluate (to leading order at least) which I have seen no mention of in standard textbooks. I want to evaluate an integral of the form $$ \int_{-1}^1 h(x)…
OmniJames
  • 11
1
vote
1 answer

big O notation - explain the equality

$$\sum\limits_{i = 1}^{\log n} {\sqrt {{2^i}} } = O(n) $$ OK, So I understand the equality, but I don't know how to prove it. For my understanding, I need to show that the left side is $\le$ the right side multiplied by a constant. Is that right? …
Daniel Gagnon
  • 535
  • 3
  • 11
1 2 3
…
74 75