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

Big - Oh proof $n^{2^n} = O(2^{2^n})$

But the book asks me to prove that it's correct: $$n^{2^n} + 6*2^n = O(2^{2^n})$$ But I think, it's an incorrect one. Because, it's correct only for $n < 2$.
Bek Abdik
  • 443
0
votes
0 answers

Proving the sum of two functions is $\Theta$ of the max of those functions?

Suppose that the functions $\ f_1, f_2, g_1, g_2: \mathbb{N}\to\mathbb{R}$ (set of real numbers greater or equal to 0) are such that $\ f_1 \in \Theta \ (g_1)$ and $\ f_2 \in \Theta \ (g_2)$. Prove that $ \ f_1 + f_2 \in \Theta (\max\{\ g_1,…
muros
  • 417
0
votes
1 answer

How to define theta in terms of omega and O?

I am trying to prove some logical stuff using the definitions of BIG O, BIG Theta and BIG Omega. Unfortunately I am a bit confused. And how can we represent Θ in terms of of those other notations? Answer: f(n) ∈ Θ(g(n)) <=> f(n) ∈ O(g(n)) and f(n)…
JOX
  • 1,509
0
votes
2 answers

Prove $10^3n^4+10^{-3}2^n=\mathcal O(2^n)$

Prove that $10^3n^4+10^{-3}2^n=\mathcal O(2^n)$ I started this proof by trying to use induction, although as I put in $n=1$, although this gives: (when $n=1$) $1000.0002<2$ This is clearly untrue and I am not sure what method I can use to try and…
user2958268
  • 157
  • 1
  • 2
  • 8
0
votes
1 answer

Asymptotic distribution of $\left(1-\frac{1}{n}\right)^{n\bar{X}_n}$

Suppose $X_1,X_2, \cdots$ are i.i.d. observations from a $Poisson(\lambda)$ distribution. Define $\bar{X}_n=\sum_{i=1}^nX_i/n$. What will be the asymptotic distribution of $\left(1-\frac{1}{n}\right)^{n\bar{X}_n}$? I have solved this problem,…
QED
  • 12,644
0
votes
1 answer

Big Oh and Big Omega clarification

Can I get an explanation of: Can g(n) be Big O of $n^{2}$ and also the Big O of $n^{3}$? (at the same time) Can g(n) be Big Omega of $\Omega (n)$ and also be the Big O of $n$?
GivenPie
  • 479
0
votes
1 answer

Is there a closed form for...

I was working on an analysis question, and was wondering if there's a closed form for $\sum_{i=0}^{log(n)}(1/2^i)log(i)$? Unless I have made a mistake, I am trying to show that $n\sum_{i=0}^{log(n)}(1/2^i)log(i) \in \Theta(n)$. Thanks!
Nizbel99
  • 907
0
votes
1 answer

Question about Big-O notation

I'm learning Big-O notation in school and my friend and I have a hard time understanding some parts of it and we don't agree on some answers in the exercises. There are two cases on which we don't agree, and they are particularly easy ones. The…
JPInglio
  • 3
0
votes
1 answer

What is $O(\sqrt{2^n}n^2)$?

What is $O(\sqrt{2^n}n^2)$? Is it $O(2^n)$, or does the square root cause it to be reduced? I'm trying to analyze an algorithm that I came up with, and if it still has exponential time cost, I'm going to have to try harder. Thanks!
Newbie Aspiring Programmer
  • 145
0
votes
1 answer

Show $5 \cdot 4^{\log_{2}{n}}$ is $\Theta(n^{2})$.

I'm having trouble working out the algebra for this problem. I know that we need to show $\exists c$ s.t. $5 \cdot 4^{\log_{2}{n}} \leq c \cdot n^{2} \forall n \geq n_{0}$, and also the other direction.
Samuel
  • 87
  • 3
0
votes
1 answer

Big theta for a S(n)

Consider the following function: $$S(n)=1+c+c^2+⋅⋅⋅+c^n,$$ where c is a positive real number. (A) This function is the sum of a geometric series. Give a precise closed-form formula for S(n), interms of c and n, in the case where c≠1. which is…
notamathwiz
  • 996
0
votes
1 answer

Prove: $\theta(n^2)+O(n^3)\subset O(n^3)$

I believe that my understanding of this question is incorrect, so any help would be appreciated. The Question: Prove: $\theta(n^2)+O(n^3)\subset O(n^3)$ Note that for this problem, you are proving that the set of functions on the left hand side is a…
Jan Christian
  • 1
0
votes
1 answer

Analysis of the limiting behavior of a certain expression

Apologies in advance if this is too easy of a question, but as an engineer, I am out of my depth. I am interested in the conditions under which the following expression approaches to $0$: $$1 - \left[1 - (1- e^{-a/b} )^c…
John J. Neal
0
votes
2 answers

Proof of $\Theta (n^2) + O(n^3) \ne O(n^3)$

This is a homework question. I have proved before that the sum of the terms on the left-hand-side are a subset of $O(n^3)$, but I have not proved that the two terms are not equal (or whether that was a strict subset, as the $\ne$ implies). I'm not…
user473973
  • 207
0
votes
0 answers

Asymptotic complexity of exponential function multiplied by logarithm and factorial.

I got this two functions to compare in preparation for a test: $$ 2^n \cdot \ln(n^2) $$ and $$ 2\cdot n!+4\cdot n^2. $$ I know that second function I can count as if it was just $n!$. But I still don't know which of these functions grow…
xaBBSks
  • 1
1 2 3
…
74 75