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

Compute using big-o

Assume that $a<0$ and that for $N$ large we have $a_N= \frac{\exp(Na)}{N} (1+o(1)) + O(\frac{1}{N})$. Can I write that $a_N$ is equal to $\frac{\exp(Na)}{N} (1+o(1))$ ? since both terms are of order $O(\frac{1}{N})$. My question must be easy but I…
vggls
  • 317
0
votes
0 answers

The asympotic distribution of a sequence of estimators

Here's the question Consider a sequence of estimators $X_{i}=X_{1},X_{2},...,X_{N}$ for $i=1,...,N$. Each estimator is resulting from a sample $j=1,...,n$. For each estimator $X_{i}$ the asymptotic normality is satisfied, as $n \rightarrow…
Konstantinos Gk
  • 1
  • 1
0
votes
1 answer

For $f(n)$ find a simple $g(n)$ such that $f(n)=\Theta(g(n))$

I have to find a specific $g(n)$ such that $f(n)=\Theta(g(n))$. $$f(n) = \sum_{i=1}^n3(4^i)+3(3^i)-i^{19}+20$$ I suppose that this can be solved as integrating this formula, but i don't know how and why we can make transition between sum and…
Igor Konoplyanko
  • 105
0
votes
1 answer

Big O confusion about upper bound of an algorithm

I dont know why I am getting confused about this as this is relatively simple but I am going to ask anyway... Consider the following algorithm: Given a value k, compute ak, and binary search for ak in an array of size N. Consider the fact that…
Matt Sigfried
  • 1
0
votes
0 answers

Find the leading behavior as $x \to 0+$ of $\int_{0}^1 \frac{e^{-xt}}{1+t^2} dt$

I'm having trouble starting with this problem. I was thinking of using the Laplace method, but that requires $x \to \infty$. Is there another method that works for $x \to 0$?
p3ngu1n
  • 589
0
votes
2 answers

Asymptotic upper bound in Big-O for $T(n)=T(n-1)+3n-5$. Proof using induction

I need to prove using induction Asymptotic upper bound in Big-O for $$T(n)=T(n-1)+3n-5$$ So I tried expanding $$\begin{align} T(n) &= T(n-1) + 3n - 5 \\ &= T(n-2)+ 2(3n-5) \\ &= T(1) + (n-1)(3n-5) \\ &= 3n^2-8n+6 \end{align}$$ Then I tried…
Jiew Meng
  • 4,593
0
votes
1 answer

Find asymptotic upper bound of Pascal Triangle

I was basically given a Pascal Triangle formula and asked to provide an asymptotic upper bound. I have done some work and ended with expression below ${n^k} \ge {n(n-1)^{(k-1)}}$ now I am trying to justify that LHS $\ge$ RHS is always true for all…
DSt_FTW
  • 41
0
votes
1 answer

if $a= O(N^2)$, can I also say $a=O(N^4)$?

if $a=O(N^2) $ then according to the big oh definition I didn't see why we can't say $a= O(N^4)$ or $= O(N^8)$
goon
  • 3
0
votes
1 answer

Function growth: $n!$ vs $n^{\log n}$

I have a problem where I have to compare two functions and tell which one grows faster: $$f(n) = n!, \quad g(n) = n^{\log_2n}.$$ However, I do not know how to tell which one is greater or reduce them with the limit definition. If I decompose both…
Louis-Vincent Boudreault
  • 13
0
votes
0 answers

Equations of asymptotic notations

Prove that $$ n^2 \cdot (1 + o(1)) = \Omega(n^2) $$ I'm having problems interpreting the LHS of this equation, since we are multiplying a function with little oh.
Bhishmaraj
  • 101
0
votes
1 answer

Argue whether $\frac{1}{x}\ln(\ln(x))=o(\ln(x)/x)$ as $x\to\infty$ (or not).

I am just wondering whether $$ \frac{1}{x}\ln(\ln(x))=o\left(\frac{\ln(x)}{x}\right)\text{ as }x\to\infty. $$ This is little-o-notation, meaning I have to show that for every positive constant $\varepsilon$ there exists a constant $N$ such…
Rhjg
  • 2,029
0
votes
1 answer

Summation formula without a variable specified

I'm attempting to solve this problem, and I've reached an impasse. Because I'm attempting to solve for the first value. $$ \sum_{i=1}^N N^3 = \left( \sum_{i=1}^N i \right)^2 $$ I then get $(N(N+1)/2)^2$ which then expands to $(N^4 + 2N^3 +…
kyle newton
  • 15
0
votes
1 answer

Showing that ${q-k \choose z-k} = {q \choose z}\frac{z^k}{q^k}(1 + o(1))$.

I am trying to understand how an equation from a research paper is derived. Suppose that $q$ is a prime power, and for functions $f$ and $g$ of $q$, we write $f = o(g)$ when $\lim_{q \to \infty} f/g = 0$. Further, suppose that $t$ and $k$ are…
David Smith
  • 530
  • 1
  • 4
  • 10
0
votes
0 answers

Prove $ \forall c \in \mathbb{R}^{+}, \forall B \in \mathbb{N}, \exists n \in \mathbb{N}, (n \geq B) \wedge (\sqrt{2n} > c \ln(n+2)) $

So far I've proved the following: $2n \geq \ln(2n) > \ln(n+2)$ for $n \geq 3 $ The proof must be without the use of calculus but I have no idea on how to proceed.
user92627
0
votes
5 answers

How to prove that $\log_2(n!) = \Theta(n\log_2[n])$?

My first thought was to use $$\lim_{n\rightarrow\infty}\frac{n!}{n^n} = 0$$so I thought it should be $$\log_2n!=O(n\log_2n=\log_2n^n)$$ but I was told that $$\log_2n!=\Omega(n\log_2n)$$ is also true. So per definition I have to find $\alpha>0$ s.t.…
nakajuice
  • 2,549
1 2 3
…
74 75