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
3answers
50 views

Prove line asymptotic to curve

I have a function denoted as: $f(x) = \frac{x}{1+e^\frac{1}{x}}$ I want to prove the line: $g(x)= \frac{x}{2} - \frac{1}{4}$ Is asymptotic (slant asymptote) to the above function when approaching ...
0
votes
3answers
38 views

Asymptotic notation (big Theta)

I'm currently in the process of analyzing runtimes for some given code (Karatsuba-ofman algorithm). I'm wondering if I'm correct in saying that $\Theta(\left\lceil n/2\right\rceil) + \Theta(n)$ is ...
1
vote
1answer
57 views

Big-theta notation

I was wondering about big-theta ($\Theta$) notation. A) Is $\Theta(n/2) \leq \Theta(n)$ for $n$ being an integer? I know that $n/2 = O(n)$, but does it also mean that $\Theta(n/2) \leq \Theta(n)$? ...
2
votes
3answers
40 views

Lower bound for the falling factorial $(2n)_{n}$

I'm looking for a lower bound for the falling factorial $$(2n)_{n}:= \frac{(2n)!}{n!}$$ I saw on Wikipedia that $n! > \sqrt{2{\pi}n}(\frac{n}{e})^n$ . So I assume that a possible lower bound ...
1
vote
1answer
29 views

Dealing with floor function in binomial coefficients

I'm trying to estimate $\binom{n}{\left \lfloor{\alpha n}\right \rfloor }$ asymptotically using Stirling's formula. However, I'm a little lost with what to do about the floor function here. In the ...
1
vote
1answer
34 views

Stuttering Subsequence Problem - Explain the example

I'm reading an article that deals with solving the stuttering subsequence problem in $\Theta (n)$. The article can be found here: http://www.cse.yorku.ca/~andy/pubs/Stutter.pdf Some background on ...
0
votes
3answers
48 views

Why does $\lim_{ t\to 0} \frac{o(t^2)}{t} = 0$?

Why does $\lim_{ t\to 0} \frac{o(t^2)}{t} = 0$? $\sqrt t = o(t^2) \implies \lim_{t\to 0} \frac{\sqrt t}{t} = \infty$ Maybe I don't understand completely the little-o notation.
2
votes
1answer
44 views

I need to show the following two limits

First, for $a>-1$: $$\lim_{n\to\infty}\frac{a+1}{n^{a+1}}\sum_{j=1}^nj^a = 1$$ Second, for $p>0$: $$\lim_{n\to\infty}\frac{e^a-1}{e^{a(n+1)}}\sum_{j=1}^ne^{aj} = 1$$ In particular, why do we ...
1
vote
1answer
16 views

Is Θ(⌈x/4⌉) = Θ(x)?

I'm currently working on aysmptotic notation. I know the basic laws of big theta, O, and omega. But I'm having a little confunsion in understanding simplifying the expressions (if that's even ...
2
votes
0answers
14 views

Leading behaviour of DE at infinity

This is taken from the book of Bender and Orszag, problem 3.44. Find the leading behavior as $x\rightarrow+\infty$ of the differential equation: $x^3y'' - (2x^3 -x^2)y' +(x^3-x^2-1)y=0$ Explain ...
0
votes
0answers
12 views

How to find asymptotic cost of matrix filling algorithm . Big O Notation

So I have a list X of N strings each of length M that will be called x_i for the ith index in X Example ...
0
votes
0answers
28 views

What are some examples of asymptotic expansions of integrals displaying the Stokes phenomenon?

With the term Stokes phenomenon we refer to how the asymptotic behaviour of a function can differ in different regions of the complex plane. What are some examples of asymptotic expansions of ...
4
votes
1answer
91 views

Asymptotic evaluation of integral of algebraic function

I am wondering what techniques exist for the asymptotic evaluation of integrals. Consider the integral $$ I(\lambda) = \int_1^\lambda dx \sqrt{1-\frac 1 x} = \sqrt \lambda \sqrt{\lambda - 1}- ...
7
votes
2answers
157 views

Asymptotics of $\int_{0}^{+\infty}\!\!\frac{dx}{\sinh^2(\epsilon \sqrt{x^2+1}) } $ for $\epsilon$ near $0$

How to find an asymptotic expansion, for $\epsilon$ near $0$, of the following integral $$ I(\epsilon):=\int_{0}^{+\infty}\frac 1{\sinh^2 (\epsilon \sqrt{x^2+1}) } {\rm d}x. $$ As $\epsilon ...
1
vote
1answer
37 views

Big-O Constants Rule Question for not-monotonically non-decreasing functions

I know that for positive monotonically non-decreasing functions, f(n) and g(n), f(n) = O(g(n) + c) entails f (n) = O(g(n)) Why does this always true only for ...
3
votes
1answer
43 views

Algebraic number with bounded coefficients

How many algebraic numbers $z$ are there satisfying $P(z)=0$ where $P(z)$ is some polynomial with integer coefficients of degree less than or equal to $n$ such that the absolute value of every ...
2
votes
1answer
18 views

Expansion of cumulant transform

Verify the following expansion for a cumulant generating function of a random variable $X$. \begin{align} \kappa(t) & = \mu t + \frac{1}{2}\sigma^2t^2+\frac{1}{6}\rho_3\sigma^3t^3 + ...
1
vote
1answer
93 views

Complete expansion of Laplace integral

Let $\varphi \in C^\infty (\mathbb R^n ;\mathbb R)$ such that 1) $\varphi(0)=0$ 2) $\varphi(x)>0$ on $\mathbb R^n\setminus 0$ 3) $\text{Hess}_{\varphi}(0)>0 $ and let $B_1(0)$ be the ...
4
votes
1answer
328 views

Laplace integral and leading order behavior

Consider the integral: $$ \int_0^{\pi/2}\sqrt{\sin t}e^{-x\sin^4 t} \, dt $$ I'm trying to use Laplace's method to find its leading asymptotic behavior as $x\rightarrow\infty$, but I'm running into ...
6
votes
2answers
92 views

Asymptotic form of the integral $\int_{0}^{\infty} dx ~ \sqrt{x^2 + wx} ~ e^{-ixs}$ for $s \to \infty$

I would like to find an asymptotic form of the following integral when $s \to \infty$ ($s$ and $w$ are positive) \begin{equation} \int_{0}^{\infty} dx ~ \sqrt{x^2 + wx} ~ e^{-ixs} \end{equation} I ...
3
votes
0answers
35 views

How does the Stokes phenomenon appear in the asymptotic expansion of $\int_0^\infty \frac{e^{-zt}}{1+t^4} dt$ for $z \to \infty$?

Consider the asymptotic $z \to \infty$ behaviour of the function $$ \tag 1 I_1(z) \equiv \int_0^\infty \frac{e^{-zt}}{1+t^4} dt.$$ This converges for $\Re(z) > 0$, and the asymptotic expansion $$ ...
1
vote
2answers
218 views

Asymptotic Behavior of the solution of the DE $y'=-2-y+t$ for $t \to \infty$

I'm new to differential equations, so any help will be grateful. I've been looking at this problem: Examine the slope field of the following differential equation. Based on the direction field, ...
0
votes
0answers
38 views

How to determine a Big-O estimate for an algorithm

This question has been mentioned in the forum but with a different approach. I need to determine a Big-O estimate for the number of operations of the algorithm below taking into account only additions ...
3
votes
3answers
80 views

Propose an algorithm to find a “celebrity”

A celebrity is a person that everyone knows, but he doesn't know anyone. If we think of a group of people as a graph, where if there is an arrow from $A$ to $B$ that means "$A$ knows $B$", then a ...
1
vote
1answer
76 views

Asymptotic expansion of $(1+\frac{t}{n})^{-n-1}$ at $n \to \infty$

I'm reading through a proof in Analytic Combinatorics by Flajolet/Sedgewick and I have come across this: We have the asymptotic expansion: ...
3
votes
1answer
219 views

Proof of the asymptotic expansion $ \int_1^x f(t) e^{i g(t)} dt \sim \frac{f(x)}{i g'(x)} e^{i g(x)}$ for $x \to \infty$

Here is an exercise from Dieudonné. He suggests to "perform integrations by part". Let $f, g$ be positive $C^\infty$ functions, $F(x)=\int_1^x f(t)dt$ and assume that $\int_1^\infty f(t) dt = ...
5
votes
1answer
185 views

Asymptotic expansion of $\sum_{k=0}^n \frac{\ln(k+x)}{(k+x)}$ at $n \to \infty$

Can someone help me get an asymptotic expansion for $$\sum_{k=0}^n \frac{\ln(k+x)}{(k+x)}$$ at $n=\infty$, where $x$ is fixed, I need it with accuracy up to like $O(n^{-3})$, I expect there to be some ...
1
vote
1answer
29 views

Why do O(logn) & O(exp(n)) Have Polynomial & Non-Polynomial Running Time Complexities Respectively Despite Their Taylor Series?

I understand that a function, say $f(x)$, belongs to a class $O(g(x))$ iff: $$ \exists k > 0 \ \ \exists \ \forall n > n_0: |f(n)| \leq |g(n) \cdot k| $$ I also know that $log(x)$ is has ...
1
vote
1answer
24 views

Growth Rates of F(n) vs. F(n) + F(n-1) + … F(1)

I am trying to understand growth rates between a function and its sum recursively. For example I understand that if: $F(n) = n$ Then the sum $n + (n - 1) + ... 2 + 1 = \frac{n(n-1)}{2}$ which is ...
1
vote
0answers
40 views

Algorithm for matrix addition and multiplication

Let $m$, $n$ be integers such that $0 \leq m,n < N$. Define: Algorithm A: Computes $m + n$ in time $O(A(N))$ Algorithm B: Computes $m \cdot n$ in time $O(B(N))$ Algorithm C: Computes $m\bmod n$ ...
5
votes
2answers
134 views

Asymptotic expansion of the integral $\int_2^\infty \frac{x^t}{\ln(t)} dt$ for $x \to 1$

If we define $$F(x)=\int\limits_{2}^{\infty}\frac{x^t}{\ln(t)}dt$$ I'm interested in the asymptotic expasion of $F$ as $x$ approaches 1. I'm pretty sure this integral has no elementary ...
4
votes
1answer
262 views

Asymptotic expansion of the integral $\int_2^x \frac{e^t}{t} dt$ for $x \to \infty$

Hello I wonder if there is any asymptotics known for such integral: $$ I(x) = \int_2^x \frac{e^t}{t} dt \qquad\text{when $ x\to+\infty $}. $$ Thank you very much.
10
votes
3answers
319 views

Asymptotic expansion of the integral $\int_0^1 e^{x^n} dx$ for $n \to \infty$

The integrand seems extremely easy: $$I_n=\int_0^1\exp(x^n)dx$$ I want to determine the asymptotic behavior of $I_n$ as $n\to\infty$. It's not hard to show that $\lim_{n\to\infty}I_n=1$ follows from ...
1
vote
1answer
45 views

Asymptotic expansion of the integral $\int_0^1 e^{-x/t} dt$ for $x \to 0$

How to get the asymptotic expansion for the integral $$\int_{0}^{1}\exp(-x/t)dt$$ in the limit $x\rightarrow 0$ ? I took $x/t=u$ and did integration by parts (IP) but if I keep doing IP, I get a ...
2
votes
1answer
360 views

Asymptotic expansion of the integral $\int_0^\infty e^{-xt} \ln(1+\sqrt{t}) dt$ for $x \to \infty$

Consider the following integral: $$ \int_{0}^{\infty} e^{-xt} \ln(1+\sqrt{t})dt $$ Calculate its asymptotic expansion to ALL orders as $x\rightarrow\infty$. It seems the natural thing to do is ...
5
votes
2answers
151 views

Proof that $J_{\nu}(x) \sim (x/2)^\nu / \Gamma(\nu+1) \; \text{as} \; \nu \rightarrow \infty$

I'm working through the exercises of Bender and Orszag's famous book, but I got stuck in 6.25 (a), in which it is asked to prove that $$J_\nu (x) \sim (x/2)^\nu / \Gamma(\nu+1) \; \text{as} \; \nu ...
0
votes
2answers
29 views

Please provide additional information for a Big-O problem solution

I am studying a Big-O example but I just do not get the idea. I have already seen that this question was asked in this forum but I am still confused. Can someone please provide another explanation so ...
0
votes
0answers
34 views

About growth rate of function

Suppose the function $ d(T)→\infty $as $ T→∞ $, what is the appropriate growth rate of $ d(T) $ in order that $ d(T)^{2d(T)-1}/T^c→0 $ with $c$ being a constant? Thanks very much for your kind help. ...
0
votes
3answers
110 views

Recurrence $T(n) = T({2n\over5}) +n$ using Master Theorem

Solve the recurrence $$T(n) = T\left({2n\over5}\right) +n$$ My attempt: $a=1$,$\ b=\frac 52$, $f(n)=n$ For the most part I believe that is correct. Now I was wondering if my math is correct in ...
3
votes
2answers
158 views

Find the asymptotic tight bound for $T(n) = 4T(n/2) + n^{2}\log n$

Find the asymptotic tight bound in $$ T(n) = 4T\left(\frac{n}{2}\right) + n^{2}\log n. $$ where $ \log n= \log _{2}n $ and $T(1) = 1$. I should solve this using all three common methods: iteration, ...
3
votes
1answer
35 views

How to give an upper bound for a solution of $T(n) = T(0.25n) + T(0.75n) + O(n)$?

We have an algorithm which can be described the recurrence formula: $T(n) = T(\frac{n}{4}) + T(\frac{3n}{4}) + O(n)$ and for $n\le 100$: $T(n) = O(1)$. How to show that $T(n) = O(n \log n)$? ...
1
vote
1answer
64 views

Using recursion tree to solve recurrence $T(n) = 3T(n/2)+n$

I am trying to solve the recurrence $T(n) = 3T(n/2)+n$ where $T(1) = 1$ and show its time complexity. $n$ can be assumed to be a power of $2$. So basically, I drew out the tree and found that: ...
0
votes
3answers
56 views

Showing that $4n + 3n \log_2n$ is $O(n\log_2n)$

I need to prove that: $$ 4n+3n\log_2n \text{ is } O(n\log_2n) $$ How can I find $c$ and $n_0$ for $3n\log_2n$? Also, using the big-Oh definition, I need to show that: If $g_1(n)$ is $O(f(n))$ and ...
1
vote
1answer
12 views

Is the integral finite if the integrand is $o(x^{-1})$?

According to theorem 2.2 in this file http://www.stat.umn.edu/geyer/old06/5101/notes/n1.pdf If $\lim_{x\to\infty} \frac{g(x)}{x^{-1}} =0$, nothing can be said about the existence of ...
0
votes
1answer
65 views

Elementary proof that $\omega(n)$ is bounded $\frac{\log n}{\log( \log n)}$ in the limit?

I'm trying to show that $\omega(n)$ is less than $\frac{\log n}{\log(\log n)}$ as it's stated without proof in an analytic number theory text. It's a corollary of the PNT, but I want to not use that ...
0
votes
1answer
12 views

How do I determine a percentage increase of a function caused by increasing the input?

Suppose you have algorithms with the five running times listed below. (Assume these are the exact running times.) How much slower do each of these algorithms get when you (a) double the input size, or ...
8
votes
5answers
308 views

An asymptotic term for a finite sum involving Stirling numbers

The question is a by-product at the end of this post. The following asymptotic term will ensure the convergence of some series. $$ \frac{1}{n!} \sum_{k = 1 }^{n } \frac{{n \brack k}}{k+1} = ...
2
votes
1answer
74 views

How can we compute best-case and/or average-case and/or worst-case running-time knowing some of them?

Complete the table when it is possible. $$ \begin{array}{c|lcr} \mathrm{Algorithme} & \text{worst-case} & \text{average-case} & \text{best-case} \\ \hline A & O(n) & ... & ...
2
votes
2answers
38 views

Prove $\frac{-\log(1-x)}{x(1-x)}=1+(1+1/2)x+(1+1/2+1/3)x^3+…$

Let $0<x<1$. How can i prove the following identity: $$\frac{-\log(1-x)}{x(1-x)}=1+(1+1/2)x+(1+1/2+1/3)x^3+...\ \ .$$
0
votes
1answer
59 views

How to prove a recurrence with multiple terms?

I have to prove that the recursion: $$T(n) = T\left(\frac{n}{3}\right) + T\left(\frac{2n}{3}\right) + n $$ is $$ T(n) = Θ(n*\log n)$$ As you can see, the reccurence has two different terms that ...