Questions involving asymptotic analysis, including growth of functions, Big-O notation, Big-Omega and Big-Theta notations.

learn more… | top users | synonyms (1)

5
votes
1answer
1k views

Asymptotics for a partial sum of binomial coefficients

Good afternoon, I would like to ask, if anyone knows how to evaluate a sum $$\sum_{k=0}^{\lambda n}{n \choose k}$$ for fixed $\lambda < 1/2$ with absolute error $O(n^{-1})$, or better. In ...
0
votes
1answer
305 views

Big O Notation Arithmetics

Assuming it is known that: $$ t\sqrt n = O((nt)^{2/3}+n+t)$$ How is it possible to deduce a bound on $ t $? Specifically, I need to prove that $ t = O(\sqrt n)$. This is part of a bigger question, ...
1
vote
1answer
417 views

Observed information matrix is a consistent estimator of the expected information matrix?

I am trying to prove that the observed information matrix evaluated at the weakly consistent maximum likelihood estimator (MLE), is a weakly consistent estimator of the expected information matrix. ...
2
votes
2answers
697 views

Difficulty proving a function exists in both Big $O$and Big $\Omega$

For an algorithm analysis homework assignment, I've been asked to show that $$f(n) = n{^2} + 3n{^3} \in \Theta(n{^3})$$ This means that its necessary to use the definitions of $O$ and $\Theta$ to ...
3
votes
1answer
89 views

Is it true that $\frac{n}{2}=\Theta(n)$?

This is probably a very silly question. If $h(n)=\frac{n}{2}, \ g(n)=n$, so $$ \lim_{n \to \infty} \frac{h(n)}{g(n)} = \lim_{n \to \infty} \frac{n}{2n}=\frac{1}{2} $$ so $h(n) \leq C_1 g(n), ...
0
votes
0answers
64 views

Asymptotic bounds for $\sum_{j=0}^{m}\frac{\log(n+\frac{a-j}{b+2j})}{(2t +j)^2}$

where $m <n$ and $n,a,b,m$ are positive. Any suggestion on how to approximate this sum asymptotically will be appreciated. So far I could do it in quite a rough way, by rewriting the numerator and ...
2
votes
2answers
198 views

Simplifying the generalized function $x^{\lambda}_+$ in the strip $-n - 1 < \mbox{Re}\lambda < -n$

Note: this post is a follow up to an earlier question. The (divergent) integral of $x^{\lambda}_+$ can be analytically continued into the region Re $\lambda > -n - 1$, $\lambda \ne -1, -2 , \ldots ...
2
votes
1answer
889 views

geometric series, big theta

I have a question about geometric series why is $g(n) = 1+c+c^2+....+c^n= \Theta(c^n)$ if $c>1$ I understand why it is $\Theta(n)$ if $c = 1$ and it is $\Theta(1)$ if $c <1$. But I just can't ...
2
votes
1answer
455 views

Prove $O(x)+O(x^2)=O(x^2)$ (Big O Notation)

I have to prove: $O(x)+O(x^2)=O(x^2)$ for $x\to\infty$ where "O" is the Big-O-Notation Specific functions are no problem for me, but I have some difficulties with this general form. But nevertheless ...
1
vote
1answer
126 views

Singularity analysis of integer power of logarithm ($\log^\beta (1-z)^{-1}$)

This is a theorem of Flajolet and Odlyzko (I think): Let $f(z)$ be a function analytic in a domain $$D = \{z : |z| \leq s_1, |\text{Arg}(z-s)| > \frac{\pi}{2} - \eta \},$$ where $s, s_1 > s,$ ...
12
votes
1answer
284 views

Estimating the integral $\int_0^1 (1-t^2)^{-1/2} e^{-nt} \,dt$ for large $n$.

I would like to find the asymptotic behavior of the integral $$\int_0^1 (1-t^2)^{-1/2} e^{-nt} \,dt$$ for large $n$. It seems reasonably obvious that the integral goes to zero. At least it is ...
1
vote
1answer
194 views

Linear time algorithm for $n\times n$ array of 1's and 0's

Suppose that each row of an $n \times n$ array $A$ consists of 1's and 0's such that, in any row of A, all the 1's come before any 0's in that row. Assuming $A$ is already in memory, describe a method ...
1
vote
2answers
494 views

Running time (Big O) of counting in binary

What is the total running time of counting from 1 to $n$ in binary if the time needed to add 1 to the current number $i$ is proportional to the number of bits in the binary expansion of $i$ that must ...
0
votes
1answer
340 views

did I prove this big O inequality correctly?

The problem I have is asking me if $2^{2^{n + 1}} = O( 2^{2^n} )$? This is my proof: let constant $C = 16$, and $k = 1$ such that for all $n \geq k$ let $n = 1$ 1: $2^{2^{1 + 1}} \leq C 2^{2^1}$ ...
3
votes
1answer
63 views

Heat Invariants on a one - dimensional Riemannian manifold

I am trying to understand the asymptotic heat trace expansion \begin{equation} \text{Tr}(e^{-t\triangle_g}) \backsim \sum_{k \geq 0} t^{k - \frac{n}{2}}c_{2k} \quad (t \to 0^+) \end{equation} that ...
2
votes
2answers
119 views

Series expansion of $ \int_{0}^{1} \frac{x^n}{1+x^n} \mathrm dx $

I have proved $$ \int_{0}^{1} \frac{x^n}{1+x^n} \mathrm dx \sim \frac{\ln(2)}{n}$$ How can I get further and find $ a$ such that: $$ \int_{0}^{1} \frac{x^n}{1+x^n} \mathrm ...
3
votes
2answers
487 views

Does $n^{\log n}$ or $(\log n)^n$ grow faster?

Which grows faster? $n^{\log n}$ or $(\log n)^n$ and how can we prove this? This was presented as a "challenge question" for students to try ahead of the next class meeting. Any help would be ...
21
votes
9answers
3k views

What is the purpose of Stirling's approximation to a factorial?

Stirling approximation to a factorial is $$ n! \sim \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n. $$ I wonder what benefit can be got from it? From computational perspective (I admit I don't ...
8
votes
2answers
635 views

Approximation of Products of Truncated Prime $\zeta$ Functions

The problem arose, while I was looking at products of power prime zeta functions $$ P_x(ks)=\sum_{p\,\in\mathrm{\,primes}\leq x} p^{-ks}, $$ with $k\in \mathbb{N}$ and $s=it$ with real $t$. By using ...
2
votes
3answers
228 views

Intermediate growth rates

Is there any simple function/formula $f(n)$, which eventually dominates every $cn$ for every $c$, and is eventually dominated by $a \cdot n \cdot \ln^k(n)$ for every $a,k \in \mathbb{Z}$, where ...
1
vote
1answer
80 views

Asymptotic equivalent of the law of lotto minimal value

This question is inspired by this one, where the law of the minimum $X$ of $m$ elements sampled without replacement from $\{1, \dots, n\}$ was investigated. In this question we wrote that the number ...
6
votes
1answer
2k views

Formal definition of big-O when multiple variables are involved?

(My apologies if this is a duplicate; I did some searching but didn't turn up anything else like this on the site. Please let me know if it's a duplicate and I'll gladly delete it.) I was reading up ...
2
votes
0answers
46 views

Local polynomial fitting using Taylor expansion

My question is about the usage of Taylor expansions when dealing with asymptotics in local polynomial fitting. The expressions that set me of are of the type: $$ g(X_i) = \sum_{j=0}^{p} ...
3
votes
1answer
392 views

Asymptotic behavior of a sequence given by a recurrence relation

Original problem is to determine asymptotic behavior of ${a_i}\left( t \right)$ as $t \to \infty $ given by recurrence relations ${a_1}\left( 0 \right) = 1$ ${a_1}\left( t \right) = \frac{{2t + ...
0
votes
2answers
317 views

Find value of constant factor in asymptotic notation

I have to find the value of constant factor $c_1$ and $c_2$ and $n_0$ in equation for which this equation satisfy: $$c_1\leq \frac12 - \frac3n \leq c_2$$ Here $n\geq n_0$. So for what value of ...
6
votes
1answer
184 views

Showing that $\int_0^1 x^{\lambda} [ \: \phi(x) - \phi(0)\: ] dx$ is convergent for $\lambda > -2$

Id' appreciate help understanding why the integral $$ \int_0^1 x^{\lambda} [ \: \phi(x) - \phi(0)\: ] dx $$ is convergent provided $\lambda > -2$, where $\phi \in \mathcal{D}(\mathbb{R})$. To ...
2
votes
1answer
121 views

What does it mean to select $O(k \log k / \epsilon^2)$ indices?

I'm reading [1] where some columns and rows of a matrix $A$ are selected by their leverage scores aiming to have CUR decomposition of $A$. In the paper $c$ is a value determining how many indices we ...
14
votes
6answers
3k views

Stirling's formula: proof?

Suppose we want to show that $$ n! \sim \sqrt{2 \pi} n^{n+(1/2)}e^{-n}$$ Instead we could show that $$\lim_{n \to \infty} \frac{n!}{n^{n+(1/2)}e^{-n}} = C$$ where $C$ is a constant. Maybe $C = ...
4
votes
1answer
109 views

Finding the asymptotics of a summation $\sum_{k=1}^{n}\frac{n-k+1}{k}$

Let $n\in\mathbb{Z}^{+}$ and $\displaystyle S_n = \sum_{k=1}^{n}\frac{n-k+1}{k}$. Finding $\Theta(S_n)$ PS: I found $\mathcal{O}(S_n) = n^2$. Thus, having $(n-k+1)/k = (n+1)/k -1 \leq n$. ...
2
votes
1answer
286 views

Method of matched asymptotic expansions

Consider the equation $(x+1-\epsilon)\frac{dy}{dx}+(1-\frac{1}{4}\epsilon^2y)y=2(1-\epsilon x)$ with $y(1)=1$. I am interested in finding an asymptotic expansion for the inner solution so I put ...
157
votes
3answers
7k views

How many fours are needed to represent numbers up to $N$?

The goal of the four fours puzzle is to represent each natural number using four copies of the digit $4$ and common mathematical symbols. For example, $165=(\sqrt{4} + \sqrt{\sqrt{{\sqrt{4^{4!}}}}}) ...
3
votes
1answer
303 views

predicting runtime of $\mathcal{O}(n \log(n))$ algorithm, one “input size to runtime” pair is given

I'm given the runtimes for input size $n=100$ of some polynomial-time (big-Oh) algorithms and an $\mathcal{O}(n \log(n))$ one. I want to calculate the runtimes for: $200$, $1000$ and $10000$. For the ...
4
votes
1answer
285 views

Evaluating a limit of the truncated exponential series motivated by the prime number theorem for $k$ distinct prime factors.

If $\pi_k(n)$ is the cardinality of numbers with k factors (repetitions included) less than or equal n, the generalized Prime Number Theorem is: $$\pi_k(n)\sim \frac{n}{\ln n} \frac{(\ln \ln ...
4
votes
1answer
104 views

Showing that the analytic definition of the Euler Constant is $O(n^{-1})$ [duplicate]

Possible Duplicate: Euler's Constant: The asymptotic behavior of $\left(\sum\limits_{j=1}^{N} \frac{1}{j}\right) - \log(N)$ I'm stumped by this one exercise. The question is to "Prove ...
2
votes
1answer
653 views

Proof of Chebyshev's theorem

(a) Show that $\int_2^x\frac{\pi(t)}{t^2}dt=\sum_{p\leq x }\frac{1}{p}+o(1)\sim\log\log x.$ (b) Let $\rho(x)$ be the ratio of the two functions involved in the prime number theorem: ...
2
votes
1answer
372 views

Understanding big $O$ notation.

This was a question on one of my previous exams. Sadly the solutions that were offered in class were torn off and lost at some point over the semester. Could someone guide me through the solutions ...
0
votes
1answer
174 views

Big Omega Notation

Using basic definition, we show that $n^2 - 10n = \Omega(n^2)$. For, $n \geq \frac{n}{2}$ for $n \geq 0$ $n – 10 \geq \frac{n}{2 \cdot 10}$ for $n \geq 10$ $n^2 - 10n \geq \frac{n^2 }{ 20}$ for $n ...
4
votes
1answer
117 views

Deriving an asymptotic formula

I'm doing some exercises in a book on asymptotic analysis. While I think I found a solution to this problem, I'm not entirely sure if it's correct, and I want to make sure that I know what's going ...
1
vote
2answers
120 views

Incorrect inequality after verifying a recurrence solved using the master method

I am trying to solve the recurrence $$T(n) = 4 T \Big( \frac{n}{2} \Big) + n .$$ using the master method and got $\Theta(n^2)$ using the first case theorem: If $f(n) = ...
1
vote
1answer
97 views

Asymptotic notation: Once $j$ is $\Theta(\log \log n)$

In the paper Wherefor Art Thou R3579X? they state at the end of page 5, while proving theorem 2.2, that "Once $j$ is $\Theta(\log \log n)$, each term in the sum is $O(1)$". My question is now what ...
3
votes
1answer
543 views

Prove $\sum \limits_{i=1}^n i^2 \in \Theta (n^3)$

I'm preparing for an exam, and one of the review problems is to sort functions by order of growth, and this was the only summation in it. I know that $$\sum \limits_{i=1}^n i^2 = ...
0
votes
2answers
77 views

Running times comparison

I am trying to find which of following algorithms has the smallest running time: 1) $O\left(\sqrt{q}\cdot\operatorname{polylog}(q)\right)$; is that linearithmic? 2) ...
2
votes
1answer
598 views

Prove the following: if $f(n)$ is $O(g(n))$ and $g(n)$ is $O(h(n))$ then $f(n)$ is $O(h(n))$

I understand that $f(n) \leq Ng(n)$ and $g(n) \leq Nh(n)$ so obviously $f(n) \leq Nh(n)$, but how would one go about proving this using proper semantics (using big $O$ notation)?
8
votes
1answer
177 views

Mean Value of a Multiplicative Function close to $n$ in Terms of the Zeta Function.

Let $f(n)$ be a multiplicative function defined by $f(p^a)=p^{a-1}(p+1)$, where $p$ is a prime number. How could I obtain a formula for $$\sum_{n\leq x} f(n)$$ with error term $O(x\log{x})$ and ...
1
vote
1answer
131 views

Why is this true for large enough n?

$$ \begin{align*} \Pr[\text{bin } i \text{ has at least } k \text{ balls}] &\leqslant \left( \frac{e}{k} \right)^k = \left( \frac{e \ln \ln n}{3 \ln n} \right)^{\frac{3 \ln n}{\ln \ln n}} ...
3
votes
1answer
212 views

Question on nested Big-O asymptotic notation

Assume you are given $f(x) \in O(n2^{O((\log \log n)^2)})$. My first question is what the exact definition of big-O is in case of nested functions. I have come up with the following: $\exists c > ...
1
vote
2answers
353 views

Find the asymptotic growth of $t(n)$ satisfying $t(n)=2^nt(n/2)+n$

Find $\Theta$ of $t(n)$ for $$ t(n)=2^nt(n/2)+n .$$ I can't use Master Theorem because of $2^nt$ and althought I am familiar with other methods, I can't solve it. Is there a chance solve it ...
3
votes
2answers
114 views

Integrating an asymptotic

Let $f \sim g$ mean that $f/g \rightarrow 1$ as $x \rightarrow \infty$. Does it follow that $\int_{1}^{x} f(t)\, dt \sim \int_{1}^{x}g(t)\, dt$?
2
votes
2answers
356 views

How to rigorously prove $n = o(k\log k)$ iff $k = \omega \left(\frac{n}{\log n} \right)$

How can one prove that $$ n = o(k\log k)$$ if and only if $$k = \omega \left( \frac{n}{\log n} \right) .$$ where $k$ and $n$ are functions of the same variable. Here $o$ represents the ...
3
votes
2answers
126 views

Showing $\log \frac{x^x}{x!}=O(x)$

I need to finish off a problem by showing that $\log (x^x/x!)=O(x)$. My first thought (after looking at a plot) was, "hah! this is easy...", but it appears I am unable to prove this. What I've got so ...