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

learn more… | top users | synonyms (1)

1
vote
0answers
91 views

Approximate solutions for quintic equation

The other day I asked a question in here about deriving the equations $$u^2\left(\left(1-s_1\right)+3u+3u^2+u^3\right) =\alpha\left(s_0+2s_0u+\left(1+s_0-s_1\right)u^2+2u^3+u^4\right),$$ where ...
0
votes
0answers
38 views

Additive and Multiplicative Error in $n!$ Approximation

Let $S(n)=\sqrt{2\pi n}\big(\frac{n}{e}\big)^n$ be the approximation of interest to $n!$. What are good lower and upper bounds on the following two functions $$(1)\mbox{ }|S(n)-n!|?$$ $$(2)\mbox{ ...
3
votes
2answers
143 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
84 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 ...
1
vote
2answers
69 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
1answer
109 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
1k 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 ...
4
votes
1answer
68 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 ...
0
votes
1answer
31 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 ...
2
votes
0answers
22 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
115 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
34 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 ...
4
votes
2answers
149 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
56 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
30 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
128 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
43 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
45 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
137 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
1k 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 ...
8
votes
1answer
110 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) .$$ ...
2
votes
3answers
86 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?
4
votes
5answers
117 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
211 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
99 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
14 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
42 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
31 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
77 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
46 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
49 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 ...
9
votes
2answers
115 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
39 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 ...
0
votes
1answer
131 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
25 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
42 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
142 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 ...
2
votes
0answers
68 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 ...
4
votes
1answer
75 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
37 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
346 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
37 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
139 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
817 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$ ...
13
votes
1answer
282 views

Upper bound for the widest matrix with no two subsets of columns with the same vector sum

Over at PPCG there is an ongoing contest going on to find the largest matrix without a certain property, called property $X$. The description is as follows (copied from the question). A circulant ...
0
votes
2answers
80 views

Is $x^2+25x+4 \in \mathcal{O}(x^2)$? If yes how? If no why not?

Is $x^2+25x+4 \in \mathcal{O}(x^2)$ ? if yes how ?, if no why? I know $x^2+25x+4\leq 25x^2+25x+25\leq 25x^2+25x^2+25x^2=75x^2$ for some $x$. What confuses me is $x^2+25x+4\leq 25x^3+25x+25\leq ...
8
votes
1answer
550 views

Good resource/exercises for learning asymptotic analysis?

I am studying asymptotic methods right now; things such as mellin transform, inverse mellin transform, saddle point method, laplaces method, etc... and I get very frustrated because I can't get very ...
1
vote
1answer
78 views

Why is $(\log n)^3\in O(\sqrt n)$?

Comparing the order of growth of the two functions by taking a limit and using l'hospitals rule, it seems that $\sqrt{n}$ should be O($log^3n$). Here are the steps I took: $$\lim_{n \to ∞} ...
0
votes
0answers
40 views

Laplace's Method modifications

I was wondering if there is a "Laplace's Method" to estimate, as $n \to \infty$, integrals of type $$ I_n = \int_0^\infty e^{nh(x)}g(nx) \, dx $$ where $g$ is a smooth function, that converges to a ...