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

Find the simplest $g(n)$ such that $f(n) \in \Theta(g(n))$

Let $f(n) = \sum_{i=1}^n i^{-1}$. Would the simplest $g(n)$ be $1$? If we let $g(n) = 1$, then for all $n > 1$, $g(n) \le f(n)$. To construct an upper bound, observe that since $n$ is finite, $f(n) = C$ for some $C \in \mathbb R$. (Here $C$ is the…
Vizuna
  • 1,256
0
votes
1 answer

Problem with this Big $O$ proof

I've been reading the wikipedia article about $Big O$ notation: http://en.wikipedia.org/wiki/Big_O_notation#Example, and i'm not sure about the second step in wich $6x^4 + |2x^3|+5$ turns into $6x^4 + 2x^4+5x^4$. How is it that the $x^4$ appears…
mayhem
  • 113
0
votes
0 answers

Showing that $f(x) \leq O(g(x))$.

I have two (strictly) positive functions $f(x)$ and $g(x)$ defined on $\mathbb{R}$. I am required to show that $f(x) \leq O(g(x))$ for $x \to \pm \infty$. I showed that $f(x) \leq kg(x)$ for $|x| \to \infty$. Is this enough ?
mich95
  • 8,713
0
votes
2 answers

What is the value of C in $O(x^n)$ definition?

I read the definition that $f$ is in $O(x^n)$ if $|f(x)|
user17753
  • 414
0
votes
1 answer

how far $2k+log_2(k+1)$ is to $k+log_2(k)$

Given two functions $f(k)=2k+log_2(k+1)$ and $f'(k)=k+log_2(k)$, I am wondering how far $f(k)$ is to $f'(k)$ in asymptotic notation. If $k$ is large then $log_2(k)\approx log_2(k+1)$ and $f(k)=f'(k)+k$. Does that mean $f(k)$ is $O(k)$ far from…
seteropere
  • 627
0
votes
3 answers

How is Big-O notation used in equalities?

I recently learned about big-O notation and I think I get it but in some uses it does not line up with what I think I understand it as. In the wikipedia page it calls using the form $f(x) = O(g(x))$ an abuse of notation because all it is saying is…
rtpax
  • 296
0
votes
1 answer

Big O notation - proving the relationship

Suppose that $n=O(\log_2 m)$. Let $f=O(m)$. How can we prove that $f=O(2^n)$ as well? I know that $m=2^{\log_2 m}$, but I can't simply plug $n$ there, because $n$ isn't equal to $\log_2 m$, but $O(\log_2 m)$. Can it be proven without refering to the…
user216094
  • 945
0
votes
1 answer

Summation of big oh terms

I read about asymptotic notation .I understood the limit definition of big oh notation.But while going about calculating O(1)+O(2)+.......…..+O(n),the sum comes out to be O(n ^2).Can anyone explain the same?
user1369975
  • 201
0
votes
1 answer

Relation involving little-o.

I am trying to show that the following relation holds: \begin{equation} \log(1+ax) = log(x) + o(log(x)) \end{equation} as $x\rightarrow \infty$, where $a$ a positive number. I tried using Taylor expansion but I could not come to the results. Any…
SpawnKilleR
  • 641
0
votes
0 answers

asymptotic equivalence

i have a question about asymptotic equivalence which means $ \lim_{n \to \infty} \frac{f(n)}{g(n)}=1$ with notation $f(n) \sim g(n)$. I know that the following holds: $\sum_{j=0}^{\infty} a_{jnk}(h) \sim \int_{0}^{\infty}a_{nk}(x,h)dx \hspace{0,1cm}…
user3556214
  • 88
0
votes
1 answer

Correct usage of asymptotic notation

Suppose that initially I have $c n$ objects, for some constant $c \in O(1)$, and I have a function $f$ that yields $f(k) = \varepsilon k$, (for $\varepsilon<1$), if $k \in \Omega(\log n)$, otherwise $f(k) = k$. Is it correct to say that after…
somebody
  • 1,085
  • 4
  • 11
  • 19
0
votes
1 answer

Why is $O(n^3)$ = $\Theta(n^2)$?

I have a problem $T(n) = 9T(n/3) + O(n^3)$ Answer is by Master's Theorem, second case (based on CLRS), so $T(n) = \Theta(n^3\log n)$ But this implies $O(n^3) = \Theta(n^2)$, how can this be true if the function bounded by $O(n^3)$ is $n^3$?
Jasmine Rain
  • 101
0
votes
1 answer

Little-o notation - why there's no $c$ in the definition?

http://www.stat.cmu.edu/~cshalizi/uADA/13/lectures/app-b.pdf The corresponding little-o means “is ultimately smaller than”: $f (n) = o(1)$ means that $f (n)/c \to 0$ for any constant $c$. Recursively, $g (n) = o(f (n))$ means $g (n)/ f (n) =…
user4205580
  • 2,083
0
votes
1 answer

$\frac{n^3}{\log(n)}$ tight bound by $n^3$

This seems a bit weird. I thought that $\frac{n^3}{\log(n)}$ is tight bounded by $n^3$ since its upper bound should also be $n^3$ and it's lower bound can be for example $\frac{1}{2}$ However, I realized that as $n$ grows larger, $\frac{n^3}{2}$…
q.Then
  • 3,080
0
votes
1 answer

Why is $ 2n^2\log n+3n^2 \notin \Omega(n^3)$?

Why $ 2n^2\;log\;n+3n^2 \notin \Omega(n^3)$ ? We can choose constant $c=1$ and $n\ge1$ and the inequality will be true.
Altaïr
  • 25
1 2 3
…
74 75