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

learn more… | top users | synonyms (1)

6
votes
2answers
118 views

Prove or disapprove the statement: $f(n)=\Theta(f(\frac{n}{2}))$

Prove or disapprove the statement: $$f(n)=\Theta(f(\frac{n}{2}))$$ where $f$ is an asymptotically positive function. I have thought the following: Let $f(n)=\Theta(f(\frac{n}{2}))$.Then $\exists ...
4
votes
1answer
47 views

Upper bound for $\prod_{ 5 \leq p <n} p^{\frac{n}{p-1}}$

Does anyone know how I could get a good upper bound for the following: $$R := \prod_{\substack{ p \; \text{prime} \\ 5 \leq p < n}}p^{\frac{n}{p-1}}$$ I'm not that skilled at asymptotic analysis ...
1
vote
1answer
23 views

Simplifying $f(n)$ by substituting, for $n$, an appropriately chosen function $n(x)$ to observe limiting behaviour of $f(n)$. Is this justified?

Say, I'm comparing two functions $f(n) = (ln(n))^2$ and $ g(n) = n^{0.01}$ as $n \rightarrow \infty$, by evaluating $\lim_{n \rightarrow \infty } \frac{f(n)}{g(n)} = \lim_{n \rightarrow ...
0
votes
0answers
8 views

Comparing Growth Rates

Suppose I want to compare the growth rate of some function $f(x)$ as $x\to a$ and another function $g(x)$ as $x\to b$. How do I go about doing that? For example, I want to decide whether ...
3
votes
1answer
70 views

Estimating an unusual infinite sum

I came across the following summation, which I would like to estimate. I only need an answer which is correct up to a constant multiple; one can assume that $a, b, c$ are real numbers in the range ...
0
votes
1answer
37 views

Name of the difference between an asymptote and the curve that approaches it

Consider a function, say a hyperbola, and its asymptote. Is there a specific term for the difference between the two? Answers specific to hyperbola, as well as answers about general terminology, are ...
0
votes
0answers
21 views

finding the n in Aymptotic notations

consider any quadratic function $f(n) = an^2 + bn + c$, where a, b, and c are constants and $a > 0$. Throwing away the lower-order terms and ignoring the constant yields $f(n)= \theta(n2)$. ...
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
40 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
44 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
33 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
38 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
46 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
16 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
26 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
31 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
92 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
160 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
45 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
20 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
94 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
335 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
94 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
41 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
263 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
51 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
92 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
78 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
222 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
188 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
31 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
26 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
51 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
267 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
321 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
50 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
372 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
152 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
33 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
112 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
171 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
36 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
75 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
57 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 ...