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

learn more… | top users | synonyms (1)

2
votes
1answer
94 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: $(1+\frac{t}{n})^{-n-1}=e^{-(n+1)\log(1+\frac{t}{n})}=e^{-t}...
3
votes
1answer
227 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
200 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
78 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
35 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 $O(...
1
vote
0answers
224 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
151 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 anti-...
4
votes
1answer
277 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
350 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
58 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 ...
3
votes
1answer
454 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
165 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
89 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
39 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
145 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
271 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
104 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
177 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
64 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
20 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 $\int_a^\...
0
votes
1answer
83 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
135 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
338 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
102 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
70 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
114 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 ...
1
vote
1answer
61 views

Asymptotic and 3-SAT problem in Algorithm Course

my TA says just one of the following is True, anyone could describe me some detail about following three lines? 1- if $f_i$ be a function of natural numbers to natural numbers and $f_i(n)=O(n)$ then ...
1
vote
1answer
93 views

Probability of picking each of m elements at least once after n trials.

Suppose I have 10^9 distinct elements, and an equal probability of picking each one in a given trial. How many trials must be conducted for the probability of having picked every element at least once ...
0
votes
2answers
21 views

How can I prove that Cx will intersect x^2

I want to disprove $ cx \geq x^2 \ \forall \ x $ where c is a real number. (i.e. show that x^2 is not O(x) ) So it seems that I can show that the two must intersect at some point ... if I divide both ...
0
votes
0answers
24 views

Different Upper and Lower Bound

Is there a function or algorithms whose upper bound and lower bound are different? For example f(X) i.e f(X) = O(X^2) and f(X) = Omega(X)
0
votes
2answers
83 views

Asymptotics of $\sum \sqrt{k}$ and $\sum (-1)^k\sqrt{k}$

I was playing around with series recently and asymptotics of $\sum \sqrt{k}$ and $\sum (-1)^k\sqrt{k}$ were required to solve another problem. I have dealt with the first one using an integral ...
1
vote
1answer
1k views

Determine the number of paths of length 2 in a complete graph of n nodes

Question: Determine the number of paths of length 2 in a completed graph of n nodes. Give your answer in Big-O notation as a function of n So I started working on this problem however I know im doing ...
1
vote
1answer
127 views

Asymptotic Expansion of an Integral involving Modified Bessel Functions

I do not have enough experience with the asymptotic expansion of integrals especially involving Bessel functions. I appreciate any feedback that you guys provide. Here is the problem. Let $a$ and $b$ ...
1
vote
1answer
31 views

Running Time Question

In what situations would a function of $\theta(n^2)$ perform better than $\theta(n \log n)$? I noticed that in comparing the two, they intersect at $n = 4$. After this, $n \log n$ takes over as ...
2
votes
1answer
101 views

Infinite sum of asymptotic expansions

I have a question about an infinite sum of asymptotic expansions: Assume that $f_k(x)\sim a_{0k}+\dfrac{a_{1k}}{x}+\dfrac{a_{2k}}{x^2}+\cdots$ with $a_{0k}\leq \dfrac{1}{k^2}$, $a_{1k}\leq \dfrac{1}{k^...
0
votes
2answers
24 views

Dominance and Big Oh problem

What is the dominant term in the following expression? 100n + 0.01*(n^2) It is confusing because the power function should be growing faster than the linear function regardless the constants. But ...
2
votes
1answer
49 views

Asymptotic solution to inequality $x < k \ln(1+x)$

What is an upper-bound on $x$, given that $x < k \ln(1+x)$? I believe that the solution is something of the form $\mathcal{O}(k \ln k)$ but I am unable to prove this. This is my first encounter ...
1
vote
2answers
1k views

Find the asymptotes of the Parametric equation?

Consider $$ x(t) = 2 e^{-t} + 3e^{2t}$$ $$y(t) = 5 e^{-t} + 2 e^{2t}$$ which represents a non rectilinear paths Horizontal and Verical Asymptotes : If $t \rightarrow +\infty \ \ or \ \ -\infty$, ...
0
votes
1answer
20 views

Confirm the answer to compute the asymptotic solution to the problem

I have the following problem The solution I derived is $O(g(n))$ where $C = 1, n > 1$. Is this solution correct ?
1
vote
1answer
78 views

Run time/Efficiency of finding Least Common Multiple

The algorithm is: $$\mathrm{lcm}(x,y)=\frac{xy}{\gcd(x,y)}$$ And we can use the Euclidean algorithm for finding $\gcd$. How is the complexity for above method $O(n^3)$, if $x,y$ can at maximum ...
2
votes
4answers
140 views

Limit and infinite sums. Finding $\lim_{x\rightarrow\infty}\sum^{\infty}_{k=1}\frac{1}{k^3 x-k^2}$

Could anyone help me with this problem. Compute $$\lim_{x\rightarrow\infty}\sum^{\infty}_{k=1}\dfrac{1}{k^3 x-k^2}$$ I don't know how to change a limit and a sum. Could you help me with this problem ...
2
votes
0answers
68 views

Picking codewords that are close

Let $[n,k,d]$ be a linear code over $\Bbb F_q$ with minimum distance $d$ and number of minimum weight codewords $N_d$. How many ways can you select codewords $c_1,\dots,c_T$ (assume $T\ll q^k$) such ...
59
votes
1answer
1k views

Why are asymptotically one half of the integer compositions gap-free?

Question summary The number of gap-free compositions of $n$ can already for quite small $n$ be very well approximated by the total number of compositions of $n$ divided by $2$. This question seeks ...
2
votes
1answer
79 views

Asymptotic bound of the series $\sum_{n\leq x}\log n / \varphi(n)$

Could someone give me a hint on the computation of the asymptotic bound for the following series $$ \sum_{n\leq x}\frac{\log n }{ \varphi(n)}\,, $$ where $\varphi(n)$ is the Euler totient function? ...
0
votes
1answer
39 views

How do limit cycles explain curvilinear asymptotes?

I'm a 17 years old and I have no clue about a concept known as limit cycles. I looked it up and I understand it represents the orbit of functions approaching other A person told me that limit cycles ...
3
votes
0answers
99 views

Effect of differentiation on function growth rate

For sufficiently "nice" functions, the differentiation operator appears to make slow growing functions grow slower and fast growing functions grow faster, with $e^x$ as a fixed point in the middle. ...
1
vote
2answers
597 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 ...
0
votes
1answer
36 views

Approximating a binomial sum over a simplex

For partial binomial sums such as $\sum_{k\le\Delta} \binom{n}{k}$ we don't tend to have closed forms. However we still know asymptotic expansions that are easy to work with. Can we do something ...
1
vote
0answers
37 views

Complexity of $T(n) = T(n-10) + \sqrt{n}$

I'm using the iteration method to find the complexity of the following recurrence (I can't use the master theorem because it doesn't match the MT form). $$ T(n) = T(n-10) + \sqrt{n} \text{ and } T(1) ...
0
votes
2answers
68 views

Big $O$ notation - $n ^ {\log n}$ versus $2^n$

I received an asymptotics question for my homework, which is to compare the orders of growth for $f(n)$ and $g(n)$ where: $f(n) = n^{\log(n)}$ $g(n) = 2^n$ I have an intuition that $f(n) = O(g(n))$,...