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

learn more… | top users | synonyms (1)

3
votes
2answers
135 views

Asymptotic development of a recurrent sequence

Let $u_0 = 1$ and $u_{n+1} = \frac{u_n}{1+u_n^2}$ for all $n \in \mathbb{N}$. I can show that $u_n \sim \frac{1}{\sqrt{2n}}$, but I would like one more term in the asymptotic development, something ...
2
votes
1answer
79 views

When is a particular sum $\Theta(n)$?

Define $$S_n = \prod_{x=1}^{\lceil\frac{n}{\ln{n} }\rceil} \left(\frac{1}{\sqrt{n}} + \frac{2x}{n}\left(z_n-\frac{1}{\sqrt{n}} \right)\right) .$$ I am trying to work out necessary and sufficient ...
0
votes
2answers
55 views

Pitfalls/subtleties of $O$ notation

What are some examples of $O$ subtleties? I'm not only thinking of the asymmetry of the $O$ relation, but of the ways in which $O$ constants can depend on nearby parameters, and the fact that the ...
0
votes
0answers
19 views

Laplace's method with nontrivial parameter dependency

I need to approximate the following integral using Laplace's method: $$ \int_0^{\infty} \frac{x^{\lambda} \lambda^{-x}}{(1+x^2)^\lambda} \\ = \int_0^{\infty} \exp\left(\lambda \log(x) - ...
0
votes
1answer
42 views

algorithmic complexity in Big O notation

Here is the function that is meant to be analyzed f1(n) 1 v ← 0 2 for i ← 1 to n 3 do for j ← n + 1 to 2n 4 do v ← v + 1 5 return v I was wondering if my ...
1
vote
1answer
696 views

Asymptotic Matching for boundary layer problem

The question asks to find a global approximation to the leading order of $\epsilon$. $\epsilon y'' + xy' + \epsilon y =0$, with boundary conditions $y(0)=1,y(1)=-1$. I assumed it's a boundary layer ...
3
votes
1answer
60 views

Given a set of powers of two, how “close” can we come to a prime?

Given a natural $n \ge 2$, we can construct a set of all powers of two from $2^n$ to $2^{4n}$: $$\{2^n, 2^{n+1}, 2^{n+2}, \dots, 2^{4n}\}$$ How close does one of these numbers come to a prime in the ...
7
votes
0answers
91 views

Given the first $n$ primes, find the least common multiple of $p_1 - 1$, $p_2 - 1$, …, $p_n - 1$

Given the first $n$ primes, we can label the $k$th prime as $p_k$. So, what is the least common multiple(LCM) of {$p_1 - 1$, $p_2 - 1$, $p_3 - 1$, ..., $p_n-1$}? In other words, if we subtract $1$ ...
0
votes
1answer
27 views

BigOh Complexity: $\frac{x^{3} + 2x}{2x + 1}$ is $O(x^2)$?

Show $\frac{x^{3} + 2x}{2x + 1}$ is $O(x^2)$ Can I do it like this? Since exponent rules/laws allow this: $\frac{x^{3} + 2x}{2x + 1}$ $=$ $\frac{1}{2}x^{2} + 2x$ Must show a constant c>0 and k ...
0
votes
0answers
25 views

When can you replace by an equivalent in a sum or inside some given function?

This question is a follow-up to this question. I was originally going to post it as a comment to robjohn, but decided it should grow into a question of its own. Write $a_n\sim b_n$ if $\lim ...
1
vote
0answers
11 views

Strategies for approximating fourier transform of $k$-th power of the $n$-th derivative of a function

For a function $f(x)$ with Fourier transform $\hat{F}(q)$, I'm interested in understanding the relationship of the Fourier transform of a power of a derivative of $f$ to $\hat{F}(q)$. Explicitly, I ...
1
vote
1answer
29 views

Proving Lower Bound on Catalan Numbers

I'm a student of computer science and was reading through my algorithms textbook about matrix chain multiplication. It brought up Catalan numbers and I was hoping to prove the lower bounds on it. This ...
0
votes
0answers
28 views

Orders of growth of typical sequences

It's been a while since I had to deal with some sort of asymptotic analysis so I am a bit rusty and trying to get the basics back together. Since I don't really know where to look for these things, I ...
3
votes
2answers
56 views

Sum of 'inverse' Normal (1/X) random variables. Equivalent resistance calculation

Consider the case of $N$ resistances $R$ connected in parallel. The equivalent resistance of such a circuit is calculated as follows $$ \frac{1}{R_{eq}} = \underbrace{\frac{1}{R} + \frac{1}{R} + ...
0
votes
3answers
42 views

Notation for asymptotic approximation

I was reading Stirling's approximation and got quite confused with the idea of asymptotic formula. So in Wikipedia it says that a function $F(n)$ of $n$ is asymptotic formula for $P(n)$ if $P(n)$ is ...
1
vote
0answers
28 views

Mutual Asymptotic analysis of the given fucntions

$ f(n)$ = $ 3n^{\sqrt{n}} $ $g(n)$ = $2^{\sqrt{n}log_2n}$ $h(n)=n! $ For all the $3$ pairs of the functions, which one is $Big-O$ of which ? I am unable to compare these functions. Edit : I ...
-1
votes
2answers
45 views

A function whose graph has vertical asymptotes at $x=+2$ and $x=-2$, and a horizontal asymptote at $y=0$

Determine a function whose graph has vertical asymptotes at $x=+2$ and $x=-2$, and a horizontal asymptote at $y=0$? I don't know to satisfy these conditions.
0
votes
1answer
41 views

How can we show that $\lim_{n \to +\infty} f(n)=+\infty$?

We suppose that $\lim_{n \to +\infty} f(n)=+\infty$. I want to prove that if $f(n)=O(g(n)), c \in \mathbb{R}$, then $f(n)+c=O(g(n))$ . $f(n)=O(g(n))$ That means that $\exists c_1>0, n_2 \in ...
0
votes
0answers
42 views

Check if $2^{2^n}=O(2^n)$

I want to check if $2^{2^n}=O(2^n)$. That's what I have tried: Let $4^n=O(2^n)$. Then, $\exists c_1>0, n_1 \in \mathbb{N}$ such that $\forall n \geq n_1$: $$4^n \leq c \cdot 2^n$$ $$$$ ...
0
votes
1answer
52 views

How to prove that $\omega (n) = O\Big{(} \frac{\log(n)}{\log(\log(n))}\Big{)}$ as $n \to \infty$?

Let $$\omega(n) := \text{number of distinct primes dividing } n. $$ How can one prove that $\omega (n) = O\Big{(} \frac{\log(n)}{\log(\log(n))}\Big{)}$ as $n \to \infty$? I know that $\omega(n)! \leq ...
0
votes
2answers
500 views

How does adding big O notations works

can someone please explain how adding big O works. i.e. $O(n^3)+O(n) = O(n^3)$ why does the answer turn out this way? is it because $O(n^3)$ dominates the whole expression thus the answer is still ...
7
votes
1answer
95 views

Asymptotics of $\prod_{x=1}^{\lceil\frac{n}{\log_2{n} }\rceil} \left(\frac{1}{\sqrt{n}} + x\left(\frac{1}{n}-\frac{2}{n^\frac{3}{2}} \right)\right) $

I am trying to work out the large $n$ asymptotics of $$S_n = \prod_{x=1}^{\lceil\frac{n}{\log_2{n} }\rceil} \left(\frac{1}{\sqrt{n}} + x\left(\frac{1}{n}-\frac{2}{n^\frac{3}{2}} \right)\right) .$$ ...
0
votes
0answers
43 views

Asymptotics of Hypergeometric series

Suppose we have a $_pF_q$ hypergeometric series that terminates for all $r>t$ for some positive integer $t$, and consider the expression \begin{multline*}\lim_{n\to\infty} ...
2
votes
3answers
67 views

Asymptotic behavior of $\sum\limits_{k=1}^n \frac{1}{k^{\alpha}}$ for $\alpha > \frac{1}{2}$

As the title states, I'm interested in the asymptotic behavior of $$\sum\limits_{k=1}^n \frac{1}{k^{\alpha}} , \alpha > \frac{1}{2}$$ for $n \to \infty $. Any hints/ideas?
13
votes
3answers
163 views

An equivalent for $\sum_{n=0}^{\infty} e^{-x\sqrt{n}}$ as $x$ tends to $0^+$

I would like to obtain an equivalent form for $$ f(x)=\sum_{n=0}^{\infty} e^{-x\sqrt{n}} $$ as $x \rightarrow 0^+$. I tried without success to "remove" the $\sqrt{\cdot}$ in the summand by summing ...
4
votes
5answers
111 views

Limit of $\sqrt[n]{(x+1)…(x+n)} - x$ as $x \to +\infty$

Let $n \in \mathbb{N}^{\ast}$. I want to determine the following limit : $$ \lim \limits_{x \to +\infty} \sqrt[n]{(x+1)\ldots(x+n)} - x.$$ Let $x = \frac{1}{t}$ with $t \to 0$. It is equivalent to ...
0
votes
3answers
41 views

Is there a function thats not in Big O and not in Big Omega?

I've been thinking about this problem for a while now but I can't fully come up with an example. It would make sense that this would exist and the only way I think it would work is if the functions ...
1
vote
2answers
89 views

Is there an “interesting” function that grows faster than $n^{kn}$ but slower than $2^{2^n}$ — relates to understanding googolplex

Motivation: I'm looking for some sort of convenient fact I can use to grasp the size of a googolplex. For a googol we observe a convenient one; it's very nearly equal to 70!. But for a googolplex I ...
0
votes
1answer
13 views

General or specific property? $(1-p)^{-x^2} = x^2 p + \mathcal{O}(p^2)$

As told in the title, I found this equality: $$(1-p)^{-x^2} = x^2 p + \mathcal{O}(p^2)$$ and wonder whether this is true in general or whether it does only hold in the context I've seen it. It comes ...
2
votes
0answers
35 views

Asymptotics for the Alternating Mertens Function

Are there any tight bounds, or any nontrivial ones actually, known for, with the lack of a better name, the Alternating Mertens Function: $$ S(n) = \sum_{k=1}^{n} \left((-1)^k \mu\left(k ...
1
vote
2answers
26 views

Prove $8n^{3}$ $+$ $√n$ $∈$ $Θ$($n^{3})$

just wondering if I proved this question correctly. Any hints, help, or comments would be appreciated. There are two cases to consider to prove $8n^{3}$ $+$ $√n$ $ϵ$ $Θ(n^{3})$ $8n^{3}$ $+$ $√n$ ...
0
votes
1answer
48 views

Big Oh notation involving $\log n!\in O(n\log n)$

I have worked hard on these questions and have found my own approach. I'm just checking if it makes logical sense for others and works. I'd appreciate any hints or better approaches. Question 1: ...
1
vote
1answer
44 views

The asymptotic behavior of $\sum_{n=1}^\infty\frac{1-\cos(x4^n)}{2^n}$ as $x\to 0$

Is there a way to show that for small $x$'s $$\sum_{n=1}^\infty\frac{1-\cos(x4^n)}{2^n}\le c\sqrt x$$ I tried Taylor expansion of $\cos$ and square root... Thank's
0
votes
1answer
31 views

Counting function for the number of zeros of a continuous positive function?

Let $f(x)$ within $x\in[a,b]$ an absolute continuous function with $f(x)\geq0$ $f(x_m)=0$ for all absolute minima $x_m$ no other zeros than at $x_m$ I am trying to define a counting function for ...
8
votes
2answers
85 views

Reworking $\sum_{n \leq x} \frac{1}{n^s}$, where $n$ is relatively prime to some fixed $k$

For a fixed integer $k \geq 1$ and real $s>0$ I want to rework the partial sums $$\sum_{\substack{ n \leq x \\ \text{gcd}(k,n) = 1 }} \frac{1}{n^s}$$ in such a way that I can find an ...
1
vote
0answers
29 views

Asymptotic behavior of the solution of a 2nd order linear ordinary differential equation

In studying the harmonic oscillator, we encounter the equation $$ f'' +(2E - x^2) f = 0$$ What is the asymptotic behaviour of the solution to this equation for a generic $E$? Any good book on ...
1
vote
0answers
37 views

Heat equation, boundary gradient singularity

Consider the Cauchy-Dirichlet problem for the heat equation in a non-cylindrical region $\Omega \subset \mathbf{R}^+ \times \mathbf{R}$: $\Omega = \{ (t,x): \; 0 \leq t \leq 1, \; x \leq ...
0
votes
1answer
81 views

Find the leading order uniform approximation when the conditions are not $0<x<1$

$$\epsilon y''+y'\sin x+y\sin 2x = 0$$ with boundary conditions $y(0)=\pi$ and $y(\pi)=0$ as $\epsilon \rightarrow 0$. I don't know how to find out where the boundary layer is? I thought initially it ...
1
vote
0answers
19 views

Find the leading order uniform approximation to the boundary value problem $\epsilon y''+y'\sin x+y\sin 2x = 0$? [duplicate]

$$\epsilon y''+y'\sin x+y\sin 2x = 0$$ with boundary conditions $y(0)=\pi$ and $y(\pi)=0$ as $\epsilon \rightarrow 0$. I don't know how to find out where the boundary layer is? I thought initially it ...
0
votes
1answer
27 views

A probably simple big $\mathcal{O}$ question

I have a probably simple big $\mathcal{O}$ question. Is the following statement correct? $$\mathcal{O}(x \log x)=\mathcal{O}(\sqrt x \log x)$$ why?
1
vote
1answer
36 views

How can I write in Landau notation (or the like) that $2^x/x$ rises almost as fast as $2^x$?

Since $2^x \not\in O(2^x/x)$, we do not have $O(2^x/x)=O(2^x)$. But since $x$ rises linearly and $2^x$ exponentially, $2^x/x$ rises almost as fast as $2^x$. Can I somehow express this in Landau ...
1
vote
1answer
45 views

Obtain the leading order uniform approximation of the solution to: $\epsilon y'' +(1+x)^2y'+y=0$?

Obtain the leading order uniform approximation of the solution to: $\epsilon y'' +(1+x)^2y'+y=0, y(0)=0 y(1)=1$ as $\epsilon \rightarrow 0$. I am completely lost. Am i right in doing this? Since ...
1
vote
0answers
50 views

$\epsilon y''+\sqrt{x}y'+y=0$, show there is no boundary layer at $x=1$ and a boundary layer of $\epsilon^{\frac{2}{3}}$ at $x=0$?

I'm so lost. If I use quadratic formula I obtain that: $$y(x) = ae^{-2\epsilon\sqrt{x}}+be^{-2x\sqrt{x}+2\epsilon\sqrt{x}}$$ with the boundary conditions $y(0)=0$ and $y(1)=1$ but how does this lead ...
0
votes
0answers
20 views

Do we recognize higher degree asymptotes beyond Horizontal and Oblique?

I am reading a textbook, and it talks about doing synthetic division in order to rewrite a function into the quotient $$R(x)=\frac{p(x)}{q(x)}= f(x) + \frac{r(x)}{q(x)}$$ Since $\frac{r(x)}{q(x)}$ ...
3
votes
1answer
54 views

Determining the asymptotics of the Summatory function of an Arithmetic Function

We define the arithmetic function: $\displaystyle f(n) = \max\limits_{p^{\alpha} || n} \alpha$, that is if $\displaystyle n = p_1^{\alpha_1}\cdots p_k^{\alpha_k}$ (prime factorization of $n$) then ...
1
vote
1answer
28 views

Subtraction of functions with BigO

When trying to assess the BigO of two functions that are added together, we take the max of the two. What happens if there is subtraction instead of addiiton? for instance: $$f(n) = bigO(n^3) $$ $$ ...
1
vote
1answer
48 views

Strict upper and lower bounds of a sum (Big-Theta)

I am trying to find a function f(k) such that $S_k=\sum_{n=1}^{k^2-1}(\lfloor\sqrt{n}\rfloor)=\Theta(f(k))$. What I have done so far: Ignoring the floor asymptotically we get: ...
2
votes
2answers
21 views

Analytic Combinatorics to asymptotically estimate the number of objects of size at most n?

I have read some bits of Flajolet's and Sedgewick's book on Analytic Combinatorics. I am quiet curious as how to asymptotically estimate the number of objects of size at most n. Suppose for example ...
3
votes
2answers
74 views

Can one apply a WKB method to an inhomogeneous first order differential equation in order to find the asymptotic expansion of the solution?

Consider \begin{equation} \varepsilon \frac{dy}{dx} = Q(x)y + R(x) \end{equation} where $\varepsilon$ is a small parameter. Can one apply a WKB method to find an asymptotic expansion for the ...
1
vote
1answer
118 views

Arrange in increasing order of asymptotic complexity

I have to arrange the above time complexity function in increasing order of asymptotic complexity and indicate if there exist functions that belong to the same order. So, my answer is $[lg(n)]^2$ ...