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

Asymptotic notations involving log and binomial coefficients

I'd like to ask for the hints for part (1) and (3) in the exercise below. I stuck completely at part (1). For part (3), I found a way to simplify $f(n)/g(n)$, but then the answer would depend on the constant $k$, and not all the conclusions about…
ensbana
  • 2,277
0
votes
3 answers

Big-O notation and growth of a squared sum

While solving a problem I got the following expression: $$ \frac{\sum_{k=1}^{n}k^{4}}{\left(\sum_{k=1}^{n}k^{2}\right)^{2}} $$ My goal is to find out if this expression goes to $0$ when $n \to \infty$. Using Faulhaulber's formula, we…
BelwarDissengulp
  • 992
0
votes
3 answers

Example of a function according to Big-Oh rules

I am having difficulty understanding the Big-Oh rules. For example , here is a question : Find example of functions ( which are not negative ) $d(n),f(n),e(n),g(n)$ such that $d(n)$ is $O(f(n))$ and $e(n)$ is $O(g(n))$, but $d(n)-e(n)$ is not…
Andy M
  • 111
0
votes
1 answer

What is the asymptotic bound on the summation?

$n + (1/2)n + (1/2)^2n + (1/2)^3n + ... + (1/2)^{log_2n}n$ Doesn't get me anywhere if I apply sum of a GP. Kind of stuck at this step.
trickster
  • 39
0
votes
1 answer

Interpreting the Time Complexity for this problem

Say I have a loop that runs, and after k iterations we find that it stops when: $\left \lfloor{\frac{n}{2^k}}\right \rfloor <1$ We solve for k to find the number of iterations like so: $0\le\frac{n}{2^k} <1$ $0\le n <2^k$ $-\infty \le log_2n…
glockm15
  • 587
0
votes
1 answer

Big "O" Notation

Prove the following statements are false: $e^x-1=\mathcal{O}(x^2)$ as $x\to 0$ $x^{-2}=\mathcal{O}(\cot x)$ as $x\to 0$ For the first one, I tried to graph them and to me it seems like $e^x-1$ blows up eventually. But I don't know how to prove it…
Thomas
  • 329
0
votes
0 answers

Choosing c and $n_{0}$ for big-oh family definitions

As far as i know the definitions are: $f(n)$ is $O(g(n))$ iff there exists $ c > 0, n_{0} $ such that $f(n) \le c \times g(n)$ holds for all $n \ge n_{0}$ $f(n)$ is $o(g(n))$ iff there exists $ c, n_{0} $ such that $f(n) \lt c \times g(n)$ holds for…
August
  • 99
0
votes
0 answers

The long time approximation from the asymptotic power series

what is the long time approximation from the following the asymptotic series function? $$t^{3\alpha-2}\sum_{n=0}^\infty\sum_{m=0}^\infty\frac{(-it^{\alpha})^{n}}{Γ(n\alpha+2\alpha)}\frac{(it^{\alpha})^{m}}{Γ(m\alpha+\alpha)}$$ Thanks for your…
karen2
  • 11
0
votes
0 answers

Big O notation question, loglinear/polynomial growth rate

I am reading about big O notation on wikipedia, and it say the following; For any $k>0$ and $c>0$, $O(n^{c}(\log n)^{k})$ is a subset of $ O(n^{c+\epsilon })$ for any $\epsilon >0$, so may be considered as a polynomial with some bigger order. I am…
Mr Martingale
  • 912
0
votes
2 answers

Question surrounding the definitions of big omega and theta

Say we have some algorithm which is known to have a worst case running time of $\Theta (n^2)$. I have been told it is possible that there could be some input which would have $O(n)$ running time but I am not sure why as by definition, $t(n) =…
Harrison W.
  • 777
0
votes
1 answer

Calculate big O notation n!

How to prove that $n!=O(5^n)$ is false? I tried to use mathematical induction, but I wasn't able to find any results.
user2134
  • 13
0
votes
1 answer

prove that $\log( f(n) )=o(\log(g(n)))$ implies $f(n)=o(g(n))$ (small o)

I think it's not true. I disprove it by assuming $f(n) = 1$, $g(n) = 2$. so $$\lim \frac{\log\left(f(n)\right)}{\log\Big(g\big(g(n)\big)\Big)} = 0$$ but $$\lim \frac{f(n)}{g(n)} = 0.5$$ which disprove it, nevertheless, I am not sure if $\log(1)…
GlobalCitezen
  • 1
0
votes
2 answers

Prove that $f\left(x\right)\ =\ \left(x+2\right)\log_2\left(x^2+\ 1\right)\ +\ \log_2\left(x^3+\ 1\right)$ is $O (x\log_2x )$

Prove that $$f\left(x\right)\ =\ \left(x+2\right)\log_2\left(x^2+\ 1\right)\ +\ \log_2\left(x^3+\ 1\right)$$ is $O(x\log_2x) $. I found this question in a book. I tried using Desmos(online graphing calculator) and found the point from where…
CuriousGeek1729
  • 27
0
votes
1 answer

Show $E[T(n)] \in \Omega(n\cdot\log(n))$

I have worked through most of the quicksort analysis below, but am stuck on how to show that $E[T(n)] \in \Omega(n\cdot\log(n))$ (i.e. part $e.$ in the image below). I am working off of part $c.$ trying to show, $$ E[T(n)] =…
sma
  • 336
0
votes
1 answer

If $f(n)$ is $\mathcal{O}(g(n))$, then prove sum of $f(x)$ is not $\mathcal{O}(n\cdot g(n))$

Given that sum of $f(n)$ is $f(1)+f(2)+\dots+f(n)$, where $n$ is natural number. I am stuck with this problem. I tried to use the definition of $\mathcal{O}$, then $$f(1)+f(2)+\cdots+f(n) \le c(g(1)+g(2)+\cdots+g(n))$$ but this seems to be going…
user533661
1 2 3
…
74 75