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

learn more… | top users | synonyms (1)

5
votes
1answer
80 views

Why does Titchmarsh say that we can move the derivative under $\frac{2}{\pi}\int_0^\infty \frac{\Xi(t)}{t^2 + \frac{1}{4}} \cosh(\alpha t) \, dt$

If we define the Riemann-Xi function as $$ \Xi(t) = \xi(\frac{1}{2} + it)$$ where $$\xi(s) = \frac{1}{2}s(s-1)\pi^{-\frac{s}{2}}\Gamma(\frac{s}{2})\zeta(s),$$ then according to Titchmarsh in his ...
0
votes
1answer
44 views

Design an algorithm - Median, computer science

I was wondering if this question belongs here or on StackOverflow, but it is a question of mathematical nature so this seems more appropriate. We have an array $S$ of $n$ different numbers $S=a_1,a_2,...
6
votes
2answers
54 views

If $f(n)$ is $O(g(n))$ and $g(n)$ is $O(f(n))$, is $f(n) = g(n)$?

Question: If $f(n)$ is $O(g(n))$ and $g(n)$ is $O(f(n))$, is $f(n) = g(n)$? I'm studying for a discrete mathematics test, and I'm not sure if this is true or false. Since Big-OH ignores constant ...
1
vote
0answers
55 views

Summation involving digamma and floor functions

I am trying to find an asymptotic expansion for the following sum: $$\sum_{n=1}^K \frac{\phi_0( 1/2+n+\lfloor(2n-1)/\sqrt{2}\rfloor)}{(4n-2)}$$ where $\phi_0$ is the digamma function and $\lfloor x\...
1
vote
1answer
130 views

Asymptotic behavior of the zeros of the digamma function

The gamma function has just one extremum on each interval $(k,k+1)$, where $k$ is a negative integer. These extrema occur at the zeros of the derivative of the gamma function. Let $z_n$ denote the $n$-...
2
votes
0answers
29 views

Asymptotic solution to $m \leqslant e^{\lambda t} (c t^q - \varepsilon)$

What is the smallest $t$ statisfying the inequality: $m \leqslant e^{\lambda t} (c t^q - \varepsilon)$, where $\varepsilon$ is arbitrary small positive number? I believe $t$ must be of the from: $$t = ...
2
votes
1answer
94 views

Simple vs compound interest rates and Taylor expansion

I am having trouble deciphering a portion from my finance text. Let $i = \text{interest rate}$, $n = \text{Some arbitrary time period}$ and $C = \text{Cash invested}$ And also $C(1+i)^n$ (...
3
votes
3answers
59 views

Rule for calculating big-O plus example I can't figure out

I have the following rule: If $f$ is $O(g)$ for ${x\to\infty}$ and $\lim_{x\to\infty}g(x) = 0$ than also $\lim_{x\to\infty}f(x) = 0$ Then my text proceeds to give an example: $\lim_{x\to\infty}\...
6
votes
3answers
172 views

Aproximation of $a_n$ where $a_{n+1}=a_n+\sqrt {a_n}$

Let $a_1=2$ and we define $a_{n+1}=a_n+\sqrt {a_n},n\geq 1$. Is it possible to get a good aproximation of the $n$th term $a_n$? The first terms are $2,2+\sqrt{2}$, $2+\sqrt{2}+\sqrt{2+\sqrt{2}}$ ... ...
3
votes
1answer
60 views

Prove that $3\log n$ is $O(\exp(0.001n))$

First time posting here. Hi math stack-exchange community! I have a bonus question on my assignment and I am having trouble proving it. The main reason is that I am only limited to using the rules ...
3
votes
2answers
115 views

Asymptotic Behaviour Of $\frac{1}{x-1}+\frac{1}{x^2-1}+\frac{1}{x^3-1} + \cdots$ as $x \to 1 $

I define $$ f(x) = \sum_{n=1}^{\infty} \frac{1}{x^n-1} = \frac{1}{x-1} + \frac{1}{x^2-1} + \frac{1}{x^3-1} +\frac{1}{x^4-1} + \frac{1}{x^5-1} + \cdots$$ and I then wish to study the asymptotic ...
2
votes
3answers
71 views

Proving that $2n^2 + n + 1 = O(n^2)$ and big O proofs in general

Alright so here's the thing, I'm in a class in Computer Science called Algorithm Analysis and it is required for me to learn Big O, Big Omega, etc. While I sort of understand what this is for, I still ...
2
votes
1answer
27 views

Estimate of tails of sums of reciprocals of a bit more than powers

The tails of sums of reciprocal powers have nice estimates: For $\alpha>1$ the integral test gives $$ \sum_{n=j}^\infty \frac{1}{n^\alpha} \leq \int_{j-1}^\infty \frac{1}{x^\alpha} dx = \frac{1}{\...
1
vote
0answers
34 views

How would you prove this Big Omega complexity?

We're given $f(n)=\frac{1}{5}n^2-30n-5$ and $g(n)=n^2$, and are asked to prove $f \in \Omega(g)$. The exercise was posted, but no solution is given (this is not an assignment question). So by ...
5
votes
7answers
479 views

Is it true that $2^n$ is $O(n!)$?

I had a similar problem to this saying: Is it true that $n!$ is $O(2^n)$? I got that to be false because if we look at the dominant power of $n!$ it results in $n^n$. So because the base numbers are ...
3
votes
0answers
39 views

Applying function to both sides of asymptotic expression

I apologize in advance if this has been asked elsewhere, but I couldn't find it. This seems like it should be a pretty simple question, but I'm drawing a blank. If you know that $f(x) \sim g(x)$, ...
1
vote
3answers
81 views

Big-O notation examples

How do I get c = 4 and n0 = 21, I understand that I could plug in different numbers till f(n) ≤ c * n for all n ≥ n0, but using f(n) how do I arrive at those numbers? ...
0
votes
1answer
161 views

Counting Primitive Operations

This is the solution I've been given for counting primitive Operation in an algorithm. I think I have my head around how all the operations are found, for instance the 2(n-1), the 2 is the primitive ...
0
votes
1answer
41 views

Number of rationals with denominator less than $N$

This is probably a duplicate since it seems like elementary number theory, but didn't find it after a cursory search. Let $r(N)$ be the number of rationals in $[0,1]$ with denominator less than or ...
2
votes
2answers
57 views

Order estimates question and big O notation

How can I show that $y(x) = 1 - \cos(x)$ is $\mathcal{O}(x^2)$ for $|x| <<1$ ? Additionally, with the $|x| << 1$ is there a precise definition? I tried to google it but nothing conclusive ...
1
vote
0answers
27 views

Asymptotic expansion of integrals of the form $\int_{\mathcal{D}} \exp(\lambda\, \phi(x))\, g(x) \,dx$ for small $\lambda.$

In the limit $\lambda\to\infty$ the asymptotic expansion of integrals of the form $\int_{\mathcal{D}}\exp(\lambda\,\phi(x))\,g(x)\,dx$ (where $\mathcal{D}\subseteq \mathbb{R^n}$ denotes the domain of ...
0
votes
2answers
212 views

Big O notation and limits

I'm wanting to take the $\lim_{x\to \infty} \frac {O(1)}{x^s}$, where $O(1)$ is Big O notation and $s>1$. I can see that it will be zero but I'm wanting to do it somewhat rigorously. Can I take the ...
1
vote
0answers
52 views

Proving $n^{10\log(n)} = O((\log^n(n))$

I need to decide which of the following is correct: $n^{10\log(n)} = O((\log^n(n))$ $n^{10\log(n)} = \Theta((\log^n(n))$ $n^{10\log(n)} = \Omega((\log^n(n))$ So I'm saying $n^{10\log(n)} = O((\...
0
votes
0answers
20 views

Question about big omega proof

I'm not sure if I should post it here or in StackOverflow, but anyway... Prove that: $n^5-2\log{n}=\Omega{(n^5)}$. Proof: We need to find $c, n_0 \geq0$ such that, for all $n \geq n_0$, $n^5-2\...
1
vote
0answers
104 views

Asymptotic expansion of a Laplace-type integral with a “manifold of maxima”

Consider the integral $$ I(\alpha)=\int_0^1 dx_1 \int_0^1 dy_1\int_{x_1}^1dx_2\int_{y_1}^1dy_2\,e^{-\alpha(x_2-x_1)(y_2-y_1)} $$ in the limit $\alpha\rightarrow\infty$. To find the asymptotic ...
4
votes
0answers
210 views

Asymptotic large order approximation for Bessel function expression

How does one find the asymptotic large order approximation for $\sup_{0\le x\le\infty} \left(\sqrt{x} J_n(x)\right)$, where $J_n$ is the Bessel function of the first kind and order $n$. This is NOT a ...
6
votes
1answer
144 views

Growth of $n!!\dots !$

The asymptotic growth of the factorial function $n!$ is famously given by Stirling's formula as $$n! \sim \sqrt{2 \pi n}\left(\frac{n}{e}\right)^n$$ Is there a similar formula for the iterated ...
0
votes
1answer
117 views

Suppose that $f (x)$ is $O(g(x))$. Does it follow that $2^{f(x)}$ is $O(2^{g(x)})$?

Suppose that $f(x)$ is $O(g(x))$. Does it follow that ? First, I start from for some $c$ is a real number. Then, I find . But, if i start from , I just find . I confused with that different form.
0
votes
0answers
22 views

How to do this asymptotic task?

Let a(n) be the amount of natural numbers, which are smaller than n, and their prime divisors are only 2 and 3. For example: 6 is good, because it only has 2 and 3 has prime divisors, but 10 is not ...
1
vote
1answer
77 views

Suppose that $f (x) =O(g(x))$. Does it follow that $\log |f (x)| =O(log |g(x)|)$?

Suppose that $f(x)=O(g(x))$. Does it follow that $\log |f (x)|=O(log |g(x)|)$? I start from $f(x)=O(g(x))$, until I get Does it mean $\log |f (x)|=O(log |g(x)|)$?
0
votes
1answer
83 views

How to solve this recurrence, $T(n) = T(\sqrt{n}) + n$ using recursive tree method?

How to solve this recurrence, $ T(n) = T(\sqrt{n}) + n $ using recursive tree method? I draw the tree and got a sum, $ T(n) = T(1) + ( n + n^{\frac 12} +n^{\frac 14}+n^{\frac 18}+\ldots +1) $ I need ...
2
votes
2answers
53 views

How to prove that $2^{n+1} = \Theta(2^n)$?

I have a problem were I need to prove big theta. $f(n) = 2^{n+1} = Θ(2^n)$. I proved that this was true for big O but I'm not sure how to go about proving big Theta.
1
vote
4answers
59 views

Does the inequality $ n! > A \cdot B^{2n+1}$ hold for sufficiently large $n$?

Suppose $A,B >0$ are given constants. Is it possible to find a large enough $n \in \mathbb{N}$ such that $$ n! > A \cdot B^{2n+1}?$$
3
votes
0answers
44 views

Proof $\mathcal{O}(f(n)) = \mathcal{O}(g(n)) \iff f(n) \in O(g(n)) \land g(n) \in \mathcal{O}(f(n))$

There is an exercise that ask me to prove this logic formula about the complexity of algorithms: $\mathcal{O}(f(n)) = \mathcal{O}(g(n)) \iff f(n) \in O(g(n)) \land g(n) \in \mathcal{O}(f(n))$ Proof:...
0
votes
2answers
22 views

How would I go about proving these.

I need to prove or disprove these two problems, but I'm not sure I did it right. $$(a).\quad f(n) = 2^n+1 = O(2^n)\\ (b).\quad f(n) = 2^n+1 = Θ(2^n) .$$ What I tried for the first one is, $2^n+1/...
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 \...
12
votes
2answers
261 views

When is this sum of perfect powers bounded

For any positive integers $n,d$, let $$ A_d(n)=\frac{\sum_{k=1}^n k^{2d}}{n(n+1)(2n+1)} $$ It is easy to see (and well-known) that for fixed $d$, $A_d(.)$ is a polynomial of degree $2d-2$. Writing $...
4
votes
1answer
62 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
204 views

Expectation and Variance of random walks

Consider random walks of fixed length (e.g. $5$) starting at node $u$ in an undirected and connected graph with $N$ vertices. If a node $k$ has $N_k$ edges, the probability of the walk reaching any of ...
3
votes
1answer
81 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,...
1
vote
3answers
68 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
76 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 ...
0
votes
1answer
91 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
82 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
58 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
89 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
47 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
45 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 ...