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
4answers
58 views

Why is $f(n) =\frac{n(n+1)(n+2)}{(n+3)}$ in $O(n^2)$?

Let: $$f(n) = n(n+1)(n+2)/(n+3)$$ Therefore : $$f∈O(n^2)$$ However, I don't understand how it could be $n^2$, shouldn't it be $n^3$? If I expand the top we get $$n^3 + 3n^2 + 2n$$ and the biggest ...
1
vote
1answer
29 views

Computational complexity and the big $\mathcal{O}$

I have a question about this Big $\mathcal{O}$ problem. I have the question down $90\%$, but the other $10\%$ isn't getting to me. I will write out the entire question and I'll point out the step, ...
1
vote
0answers
21 views

Asymptotic behavior of sums of consecutive powers (bivariate)

Are there some (bivariate) closed form formulas for the asymptotic behaviour of the sum: $$\sum_{k=1}^{n} k^d,$$ where $n$ and $d$ are large integers? I am especially interested in a lower bound of ...
0
votes
0answers
20 views

What is the sign of the generalized Stieltjes constants $\gamma_{k}(a)$?

Recall that the Stieltjes constants $\gamma_{k}$ appear as the coefficients in the regular part of the Laurent expansion of the Riemann zeta function about $s = 1$: $$ \begin{align} \zeta(s) = ...
0
votes
1answer
49 views

Differential equation how to find out bounded or not bounded

For which value of the parameter $k$ will all solutions of remain bounded as $t \rightarrow \infty$? $$u''(t)+k~u(t)=2 \sin(10t)?$$
2
votes
1answer
97 views

Why does convolution not maintain asymptotic equality of coefficients?

Assume I have four (generating) functions $f$, $f'$, $g$ and $g'$. If that is interesting, we can assume that they all share the same radius of convergence $\rho > 0$. In addition, we know that ...
2
votes
0answers
32 views

Do asymptotically equivalent coefficients survive convolution at least in Θ?

This is a follow-up question to this one where I asked if asymptotic equivalence of coefficients carried over after convolution, resp. why this was not the case. Answerer Daniel Fischer proposed that ...
0
votes
2answers
22 views

Determine whether the function floor(x) is big omega of x

I'm a little confused on what to answer to this: Determine whether the function floor(x) is big omega of x. The above function holds for integers but not for real numbers. According to the definition ...
0
votes
0answers
15 views

Lower bound for a relative of the central binomial coeff

The central binomial coefficients $\binom{2m}{m}$ have g.f. $\frac{1}{\sqrt{1-4z}}$ and lower bound $\frac{4^m}{\sqrt{4m}} \le \binom{2m}{m}$. I'm interested in a related integer series $$T(2m, m) = ...
5
votes
2answers
253 views

Big-O notation, prove the following: $\sum\limits_{k=3}^n(k^2 - 2k)$ is $O(n^3)$.

Use the definition of Big-O notation to prove the following: $\sum\limits_{k=3}^n(k^2 - 2k)$ is $O(n^3)$. Can someone please give me some hints on how to expand $\sum\limits_{k=3}^n(k^2 - 2k)$?
1
vote
0answers
44 views

Long-time asymptotic behaviour of a system of two ODEs

We have the following nonlinear ODE: $$ f' = af-bg -(f+g)^k \bigl(f'(0) +g'(0)\bigr) + f'(0), $$ $$ \bigl(G-T(x)\bigr) g' = -af+bg - g'(0), $$ where $a,b,k,G$ are constants, $f'(0)$ and $g'(0)$ are ...
2
votes
1answer
61 views
+50

Asymptotic expansion on 3 nonlinear ordinary differential equations

The 3 nonlinear differential equations are as follows \begin{equation} \epsilon \frac{dc}{dt}=\alpha I + \ c (-K_F - K_D-K_N s-K_P(1-q)), \nonumber \end{equation} \begin{equation} \frac{ds}{dt}= ...
3
votes
1answer
110 views

Asymptotics of $\sum_{n=1}^{\infty}x^{n+1/n}/n!>e^x$?

Is there a way to find precise asymptotics or better bounds of series such as $\sum_{n=1}^{\infty}x^{n+1/n}/n!>e^x$ ? Or $\sum_{n=1}^{\infty}x^{\sqrt n}/e^n$?
11
votes
3answers
304 views

Closed form for $\sum_{k=0}^{n} k\binom{n}{k}\log\binom{n}{k}$

Is it possible to write this in closed form: $$\sum_{k=0}^{n} k\binom{n}{k}\log\left(\vphantom{\Huge A}\binom{n}{k}\right)$$ Can you get something like $$n2^{n-1}\log(2^{n-1})$$
1
vote
1answer
83 views

Since $2^n = O(2^{n-1})$, does the transitivity of $O$ imply $2^n=O(1)$?

Let us assume that $f(n)=2^{n+1}$, $g(n)=2^n$ be two functions. Now, use limit to find $O(f(n))$: $\lim_{n\to\infty} \dfrac{2^{n+1}}{2^n}=2$. This is not equal to infinity, so the limit exists, hence ...
1
vote
0answers
31 views

Approximations for finite n in limit-based definition of the exponential function

The exponential function can be defined via: $$ e^x = \lim_{n \rightarrow \infty} \left( 1 + \frac{x}{n} \right)^{n} = \lim_{n \rightarrow \infty} g(x; n) $$ In my problem, I actually have the right ...
1
vote
1answer
46 views

Asymptotic behaviour of a sum

Let $p$ and $q$ be positive real numbers such that $p+q = 1$. am interested in in the large-$n$ behaviour of a following sum: \begin{equation} \sum\limits_{j=0}^{n-1} \left(1 + \frac{n-j-1/2}{j+1} ...
1
vote
3answers
47 views

Solving a Perturbed Cubic Equation

Consider a cubic equation $(1 + \epsilon)x^3 - 2ax^2 + (a - 3\epsilon)x + 2\epsilon = 0$ where $\epsilon > 0$ and $a \gg 1$. In the limit of $\epsilon \rightarrow 0$, $x(x^2 - 2ax + a) = 0$ so ...
1
vote
0answers
25 views

Question about finite sums and integer recursions.

Let $n$ be a positive integer and let $g(n)$ be a given strictly increasing integer function such that $0<g(n)<n$ for all $n$. Also the sequence $ |g(n) - n|$ is unbounded as $n$ grows. Let ...
1
vote
2answers
168 views

Finding the asymptotic behavior of the recurrence $T(n)=4T(\frac{n}{2})+n^2$ by using substitution method

I am trying to solve a recurrence by using substitution method. The recurrence relation is: $$T(n)=4T\left(\frac{n}{2}\right)+n^2$$ My guess is $T(n)$ is $\Theta (n\log n)$ (and I am sure about it ...
1
vote
2answers
38 views

Check my proof: Big O notation

I was asked the following: We are given the functions $f(n)=n^{10\log(n)}$ and $g(n)=(\log (n))^n$. Which of the following statements is true: $f(n)\in\mathcal{O}(g(n))$, $f(n) \in ...
0
votes
0answers
30 views

Is it true that $k^{\lceil f(k) \rceil}(1+o(1)) = k ^{f(k)}(1+o(1))$? [on hold]

Is it true that $k^{\lceil f(k) \rceil}(1+o(1)) = k ^{f(k)}(1+o(1))$? I think the answer is no?
1
vote
4answers
38 views

Proving Big Oh Notation

Show that $f(n) = n^{2} + 2n + 1$ is $O(n^{2})$. Sorry if this is a duplicate question or anything but I'm terribly having a hard time understanding this big-oh notation. I've looked for methods on ...
1
vote
3answers
69 views

Proving that $f(x)=2^x$ is $O(x^2)$

Can someone help me with this problem? I don't really know what to do if the x is in exponential form.
7
votes
1answer
194 views

An equivalent for $\int_0^1\left(\frac{1}{\log x}+\frac{1}{1-x}\right)^n\;dx$

Set $$ I_n :=\int_0^1\left(\frac{1}{\log x} + \frac{1}{1-x}\right)^n \:\mathrm{d}x \qquad n=1,2,3,.... $$ We have $$I_1 =\gamma, \quad I_2 =\log (2 \pi) - \frac 32, \quad I_3 = 6 \log A - ...
11
votes
1answer
282 views

Packing an infinite sequence of disks

Let $a > 1$ and $Q(a)$ denote the supremum of values of $q$ such that a countably infinite collection of disks, whose areas form an infinitely decreasing geometric progression with the start value ...
0
votes
1answer
46 views

Proof verification problem

I would like to know what is the true output, and what is the way of solving it? To me, I have got solution to be exact as Q1. Consider the following “proof” that $$ 1^k+2^k+\cdots+n^k\in ...
1
vote
1answer
11 views

Relationship between big O notation and exponential type

Let $f: \mathbb{R} \to \mathbb{R}$, $C\in \mathbb{R}$. What, if any, is the difference between "$ f = O(e^{Cx}) $" and "$f$ is of exponential type $C$"? If they're different, is it possible to ...
3
votes
6answers
524 views

Proof by contradiction that $n!$ is not $O(2^n)$

I am having issues with this proof: Prove by contradiction that $n! \ne O(2^n)$. From what I understand, we are supposed to use a previous proof (which successfully proved that $2^n = O(n!)$) to find ...
4
votes
2answers
453 views

Solving recurrences of the form $T(n)=aT(n/a)+Θ(nlgn)$

On pages 95 and 96 of the third edition of the CLRS book, we find the following, which applies here since $a=b$ is all it takes to block the application of the Master Theorem: "Although $n\lg n$ is ...
8
votes
1answer
114 views

Asymptotic Behaviour Of A Bizarre Function 2

It is well-known that $$\frac{1}{1}-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}+\cdots = \ln 2 $$ Hence $$\frac{x}{1}-\frac{x}{2}+\frac{x}{3}-\frac{x}{4}+\cdots= x\ln 2 $$ However, consider $f(x)$, where ...
4
votes
1answer
58 views

Examples of sub-exponential functions that aren't exponential functions when chained by a polynomial

Wikipedia talks about two groups of functions with asymptotic growth rates between polynomial and exponential – quasi-polynomial functions and sub-exponential functions. It only gives two ...
1
vote
3answers
44 views

Finding Horizontal/Oblique Asymptote of $y=\frac{\sqrt{x}+1}{\sqrt{x}-1}$

Is it correct to simply subsitute $\sqrt{x}$ with $x$ when finding horizontal or oblique asymptotes? The method works but I am not sure if it is formally sound enough to pass muster in an examination. ...
1
vote
1answer
59 views

Asymptotic Problem

Let us assume that $f(n)=2^{n+1}$, $g(n)=2^n$ be two functions. Now, using limit to find $\mathcal{O}(f(n))$, $\lim_{n\to\infty} \frac{2^{n+1}}{2^n}$we get 2 as answer 2 is less than infinity, so ...
5
votes
1answer
32 views

Asymptotics bound on Jacobi polynomials in the complex plane and for large $n$

Dear mathematicians and theoretical physicists, I am a theoretical physicist and I am bothering to you since I need to know some asymptotic and analytical properties of Jacobi polynomials ...
0
votes
1answer
42 views

Why, or why not, is $5^{log_3(n)} \in \mathcal{O}(n^2)$?

Why, or why not, is $5^{\log_3(n)} \in \mathcal{O}(n^2)$ ? I tried transforming the logarithm to a base of 5, so that the logarithm and power cancel each other out. However, when I try to so I get ...
0
votes
1answer
20 views

Asymptotic notation problems, am i correct??

$f(n)$ belongs to $\Theta(g(n))$ then it implies that $2^{f(n)}$ belongs to $\Theta(2^{g(n)})$. [True] $f(n)$ does not belong to $o(g(n))$ and $f(n)$ does not belong to $\omega(g(n))$ then it ...
1
vote
1answer
397 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 ...
5
votes
2answers
90 views

How is $ \sum_{n=1}^{\infty}\left(\psi(\alpha n)-\log(\alpha n)+\frac{1}{2\alpha n}\right)$ when $\alpha$ is great?

Let $\psi := \Gamma'/\Gamma$ denote the digamma function. Could you find, as $\alpha$ tends to $+\infty$, an equivalent term for the following series? $$ \sum_{n=1}^{\infty} \left( \psi (\alpha ...
2
votes
4answers
1k views

$T(1) = 1 , T(n) = 2T(n/2) + n^3$? Divide and conquer

$T(1) = 1 , T(n) = 2T(n/2) + n^3$? Divide and conquer, need help, I dont know how to solve it?
3
votes
4answers
229 views

stuck with master method

$$T (n) = 3T (n/5) + \log^2 n$$ i am trying to solve this recurrence i have been told that it is master methods case 1 but how do i compare $\log^2n$ with $n^ {\log_5 3}$
0
votes
0answers
63 views

Prove $Pr[X + Y \geq x] \sim Pr[X \geq x]$

We have two independent random variables $X_n$ and $Y_n$, where $$X_n=\sum_{i=0}^n x_i$$ and $$Y_n=\sum_{j=0}^n y_j,$$ where $x_i$,$y_j$ are (non-identically) Bernoulli distributed and independent. ...
6
votes
3answers
2k views

how to solve the recurrence $T(n) = 2T(n/3) + n\log n$

How do we solve the recurrence $T(n) = 2T(n/3) + n\log n$? Also, is it possible to solve this recurrence by the Master method?
4
votes
3answers
48 views

Show that $\frac{x^4 +7x^3+5}{4x+1}$ is big-theta($x^3$)

I'm having trouble grasping how to set these types of problems. There are a lot of related questions but it's difficult to abstract a general procedure on finding constants that give the given ...
2
votes
1answer
54 views

Prove that limits can be used for asymptotic analysis

True or false: If f(n)=$\Theta$(g(n)), then $$\lim_{n\rightarrow \infty}\frac{f(n)}{g(n)}$$ exists and is equal to some real number. I'm not sure what needs to be done to demonstrate this. I do ...
1
vote
0answers
26 views

What is the power series for a half-exponential function?

What is the power series of a half-exponential function? Half-exponential means that $f(f(x)) = y^x, y > 1$
4
votes
2answers
67 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
66 views

asymptotic behaviour of coefficients in nonnegative matrix iteration

Let $A$ be a square matrix with nonnegative integer coefficients. Is there a simple way to prove that there is a "period" $d$ such that for all $0\leq r<d$, the coefficient $a_{i,j,n}$ at position ...
0
votes
0answers
21 views

Power iteration sequemce for a special nonnegative irreducible imprimitive matrix

Let $A \in \mathbb{R}^{n \times n}$ be nonnegative irreducible matrix with maximum positive eigenvalue equal to 1. Let's assume $A$ has $h$, $h > 1$ eigenvalues $\lambda_1, \dots, \lambda_h$ with ...
4
votes
1answer
66 views

Can the master theorem be applied in this case?

I have to define an asymptotic upper and lower bound of the recursive relation $T(n)=5 T(\frac{n}{5})+\frac{n}{ \lg n}$. I thought that I could use the master theorem,since the recursive relation is ...