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

Prove that $\sum_{i=1}^n\Theta(i)=\Theta(n^2)$.

The left hand side stands for a single function $f(i)$ in $\Theta(i)$ summed over $i=1,\,2,\,3,\,\ldots,\,n$. I know it is sufficient to show that $h_1(n)\leq\sum_{i=1}^nf(i)\leq h_2(n)$ for all sufficiently large $n$, where $h_1(n)=\Omega(n^2)$ and…
Revoltechs
  • 321
  • 1
  • 9
0
votes
1 answer

Answer or Guide me Through This Question. Show that the function is ϴ(n^4) by first showing that it is O(n^4) and then by showing it it also Ω(n^4)

Show that the function $$ f(n) = \sum_{i=1}^n \sum_{j=1}^i \sum_{k=1}^j k $$ is $\Theta(n^4)$ by first showing that it is $O(n^4)$ and then by showing it is also $Ω(n^4)$. So I know that: $\sum_{i=1}^n i = \frac{n(n +1)}{2}$ which is…
Jason Kidd
0
votes
1 answer

How to obtain this inequality from a function expressed in Big O notation?

I have an asymptotic expression of the following form: $$U(r) = \rho r^{-1/2}\exp\left(\frac{ibr^2}{4}\right)\exp\left(\frac{-i\ln(r)}{b}\right)(1+\mathcal{O}(b^{-3}r^{-2})).$$ I want to get an asymptotic expression for $U(b^{-2}).$ The paper where…
Student
  • 9,196
  • 8
  • 35
  • 81
0
votes
1 answer

Asymptotic bound of $\sum_{i=0}^{\log(n)} 2^{i} \sum_{k=0}^{\frac{n}{2^{i}}} (k+2)^{2} + \theta(n)$

What is the asymptotic bound for $\sum_{i=0}^{\log(n)} 2^{i} \sum_{k=0}^{\frac{n}{2^{i}}} (k+2)^{2} + \theta(n)$?
Yashar
  • 63
0
votes
3 answers

If $f$ is big or little oh of $g$, what can we say about $a^f$ and $b^g$ for $a,b>1$?

I’m interested in what operations preserve asymptotic relationships. For example, I can prove that if $f=o(g)$ (as $x\to\infty$), then $a^f=O(b^g)$, for any bases $a,b>1$. But I think that’s the best we can say: I don’t think we can improve the…
user1435
  • 21
0
votes
0 answers

Prove or disprove: $n^{\log_2 n} = \mathcal{O}(a^n)$ for all $a > 1$

I am not sure how to solve this problem: Prove or disprove: $n^{\log_2 n} = \mathcal{O}(a^n)$ for all $a > 1$ I have tried calculating $\lim_{n\to\infty} \frac{n^{\log_2 n}}{a^n}$ to see if it equals zero (which would imply that this equals…
Peter
  • 69
0
votes
2 answers

Some asymptotics as difference tends to infinity

Let $c>0$ and $\alpha >\frac{c}{2}$. Is it true that, as $q_2-q_1$ goes to infinity, the expression $$ (q_2-q_1)e^{-\alpha(q_2-q_1)} $$ goes faster to $0$ as $$e^{-\frac{c}{2}(q_2-q_1)}?$$ I would think so: First of all, the expression converges to…
Salamo
  • 1,094
0
votes
2 answers

Dropping smaller terms in Big O notation

As I'm learning Big O notation, I'm having difficulty understanding how ALL arithmetic operations are always constant. For example, the growth rate of either O(15n) or O(150n+50) is supposed to be same as O(n): from 10 to 10^1.2 I would expect at a…
bran
  • 1
0
votes
2 answers

Asymptotic series

Could somebody explain to me why $\sum_{n=1}^\infty b^{-n^b}$ is nearly equal to $\frac 1b$ for $b>2$?
Kinheadpump
  • 1,331
0
votes
1 answer

Assume $f(n)=O(g(n))$ with $g(n)\geq 2$ for all $n$

Assume $f(n)=O(g(n))$ with $g(n)\geq2$ for all $n$ implies $f(n)+g(n)=O(g(n))$ the answer which teacher offer is false ，but I think it is true this is my think $f(n)=O(g(n))$ so $f(n)\leq c\cdot g(n)$ ,$f(n)+g(n)\leq (c+1)\cdot g(n)$ So…
TC code
  • 1
0
votes
1 answer

How to determine big O from expression?

If you have this expression: $$\frac{1+n+\left\lceil\log_2{n}\right\rceil}{1+\left\lceil\log_2{n}\right\rceil}$$ How do you obtain a big $O$ from this? I think it's just $O(\log_2n)$. Is this right?
omega
  • 751
0
votes
1 answer

Asymptotic relationship between functions

I would like to find an asymptotic relationship between those two functions, and I don't know how, can anyone tell me a few tips or a way how to do that? first pair: $$(\log n)^n \quad \text{and} \quad n^{log(n)}$$ the log base is $2$. second…
Alex K
  • 101
0
votes
3 answers

For the following function, find a function as simple as possible that reflects its asymptotic behavior

Question: For the following function, find a function as simple as possible that reflects its asymptotic behavior (use big-notation). What does as simple as possible mean to begin with? A short definition would be helpful! $$f(n) = 3^{2n-1} + 4^n +…
user9132502
  • 145
0
votes
1 answer

Find the simplest Big O estimate for this log function?

$$f(n) = \log^4(n)+\sqrt{n}$$ What I've did: $\sqrt(n)\in O(n^{1/2})$ $\log^4(n)\in O(n^{4})$ $f(n)\in O(n^{1/2} * n^4) = O(n^{9/2})$ Is this correct? Question also says to find C and K to justify my answer, how can I do this?
user9132502
  • 145
0
votes
2 answers

Are these properties of Big O valid?

I was working through the prime number theorem proof and the following questions arose. 1.) Is $f_1=f_2-\mathcal{O}(x)$ equivalent to $f_1=f_2+\mathcal{O}(x)$ for any two functions $f_1$ and $f_2$. 2.) If I can show that $\log(f_1) =…
Ryan Shesler
  • 1,498
1 2 3
…
74 75