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

learn more… | top users | synonyms (1)

0
votes
1answer
339 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
316 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
120 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
302 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
652 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
371 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
597 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
352 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 ...
2
votes
0answers
97 views

About how big is $n^0+(n-1)^1+\cdots+0^n$? [duplicate]

Possible Duplicate: Asymptotics of $1^n + 2^{n-1} + 3^{n-2} +\cdots + (n-1)^2 + n^1$ About how big is is the sum $\sum_{k=0}^n k^{n-k}$? At the least, can we get an upper bound on it that ...
2
votes
1answer
79 views

Is $n=\mathcal{O}(n+1)$?

With $c=1$ and $n_0=0$ the statement $$(\forall \mathbb{N}_0\ni n>n_0)[n\leq c\cdot (n+1)]$$ is obviously true. Does this suffice for the proof of $n=\mathcal{O}(n+1)$? Another idea was this ...
2
votes
4answers
134 views

Proving an exponential bound for a recursively defined function

I am working on a function that is defined by $$a_1=1, a_2=2, a_3=3, a_n=a_{n-2}+a_{n-3}$$ Here are the first few values: $$\{1,1,2,3,3,5,6,8,11,\ldots\}$$ I am trying to find a good approximation ...
0
votes
1answer
975 views

Compare growth rate of functions

I was given homework to sort some (14) functions in order of their growth rate. I am confused about two functions $3^\sqrt{\log n}$ and $n^{\log n}$: about where these two lie within those 14 ...
26
votes
2answers
1k views

What are the rules for equals signs with big-O and little-o?

This question is about asymptotic notation in general. For simplicity I will use examples about big-O notation for function growth as $n\to\infty$ (seen in algorithmic complexity), but the issues that ...
-1
votes
2answers
418 views

Two questions in asymptotic notation

I have to prove two equations and I can't understand them. Any help would be grateful because I have to consign the whole project in two days. These are the equations: If $f(n)=O(g(n))$ and ...
7
votes
1answer
262 views

Bounds on $\sum_{k=0}^{m} \binom{n}{k}x^k$ and $\sum_{k=0}^{m} \binom{n}{k}x^k(1-x)^{n-k}, m<n$

I've read this interesting article by Woersch (1994) dealing with approximation of binomial coefficients (rows of Pascal's triangle). I'm just wondering if similar bounds exist for partial binomial ...
2
votes
1answer
302 views

Prove that $e^{\sqrt{\log x }}=O(x^n)$

I have to prove the following: Let $n \in \mathbb{N}$. Proove: $$e^{\sqrt{\log x}}=O(x^n) .$$ I just know the definition of $O$: $f(x), g(x)$ are real functions. $f(x)=O(g(x))$ means, that for ...
2
votes
1answer
261 views

If $f(n) \in O(g(n))$, then $f(n)+g(n) \in \Theta (g(n))$

I am a total beginner with the big O and big theta notation. How would I prove the following? If $f(n) \in O(g(n))$, then $f(n)+g(n) \in \Theta (g(n))$. I am not sure how to go from the ...
1
vote
0answers
119 views

Question concerning application of l'Hôpital's rule

Prove: If g is strictly positive then $\int_{2}^{x}o(g)\,dt = o\left(\int_{2}^{x}g\,dt\right)$. I understand this question to mean: prove that $f=o(g)$ implies $F = o(G)$ and conversely. Please ...
3
votes
2answers
96 views

Is $O(\frac{1}{n}) = o(1)$?

Sorry about yet another big-Oh notation question, I just found it very confusing. If $T(n)=\frac{5}{n}$, is it true that $T(n)=O(\frac{1}{n})$ and $T(n) = o(1)$? I think so because (if ...
7
votes
1answer
244 views

Mixing two different biased coins

My problem is as follows: I have two biased coins with probabilities $p_1$ and $p_2$ of landing heads. I start with coin 1 and toss it until it lands heads. Then I swap to coin 2 and toss until it ...
2
votes
2answers
63 views

Can I simplify $\log_3{n} \cdot 2^{\log_3{n}} \cdot n$

Is it possible to simplify $$\log_3{n} \cdot 2^{\log_3{n}} \cdot n$$ I am actually trying to find the Big-O notation for this equation. But if you don't know what it is, is it possible to simplify ...