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
0answers
28 views

Merten's function

I am tasked with applying the Wiener-Ikehara Theorem to achieve a bound of little o(x) on Merten's function $\sum_{n=1}^x \mu (n)$. My problem is the Wiener-Ikehara Theorem applies to Dirichlet series ...
1
vote
0answers
32 views

Asymptotic Proof

Can someone explain this asymptotic proof to me.I am stuck at the inductive step and get lost around this step $2 × n! < (n + 1) × n!$ $$2n = o(n!)$$ True Proof: In order to $2n = o(n!)$ be true, ...
0
votes
2answers
26 views

Calculating Running Time of Recurrence Relations

I had to calculate the Running Time of the following Algorithm. ...
2
votes
1answer
50 views

How to find $s(\exp(d(x)))$ ~ $ x + 2 $?

Let $x$ be a positive real. I want to find a pair of analytic functions $s(x),d(x)$ such that $s(d(x)) = x$ and $ s(\exp(d(x)))$ ~ $ x + 2 $ More presicely I Also want : $$ \lim_{x \to \infty} ...
2
votes
2answers
17 views

Find the minimum value of $n$ such that $\sin^n(c)<\varepsilon$ for some small constant $\varepsilon>0$

Let $c$ be a constant such that $0 <c \le \pi/2$ and $\sin(c) \ne 0$. Question: What is the minimum value of $n$ such that $\sin^n(c)< \varepsilon$ for some small constant $\varepsilon >0$ ? ...
0
votes
0answers
18 views

Proving or disproving the asymptotic notations

I am looking at this questions and the proof for it and wondering how this works.Can anyone explain the answer to me or do you have any other way to answer this question.I am new to asymptotic ...
0
votes
0answers
22 views

What should be the optimal order of $x$?

Let $f(x,y) = O\left(y^{-1}x^a\exp(x^b) + x^{c}\right)$. I would like to find the optimal order of $x = x(y)$ such that $f(x,y)$ is minimized as $y\to\infty$. The problem I have is due to the ...
1
vote
1answer
34 views

is it possible to find $x$ where $y$ is equal to a whole number in a non iterative fashion

Given the equation $$\frac{635x+326}{637+x} = y$$ where $$x>0$$ Is it possible to find all positive values of $x$ (there is only one) where $x$ is positive and $y$ is a whole number. While I ...
0
votes
1answer
20 views

asymptotic complexity of functions

I'm curious if my asymptotic analysis of these functions are correct. I know the process is to strip the constants and then get to where its just comparing functions and taking limit to infinite and ...
4
votes
1answer
44 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
27 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 ...
5
votes
2answers
34 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
26 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 ...
1
vote
1answer
36 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 ...
2
votes
0answers
25 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 = ...
0
votes
0answers
12 views

Upper bound for a Selberg-type integral over a rectangular region

I am trying to estimate the values of the following integral for large $n$, $$\frac{1}{n!}\intop_{\Omega}\prod_{1\leq i<j\leq n}(x_{j}-x_{i})^{2}\,\prod_{j=1}^{n}e^{-x_{j}^{2}}dx_{j},$$ where ...
0
votes
0answers
20 views

Asymptotic analysis of $\int_{0}^{\infty} \frac{\sqrt k J^2_{\ell}(k) \sin{(\tau\sqrt k)}}{(k+1/2)^{n+2}} dk$

Question as the title showed, in which $n$ and $\ell$ are positive integers, $\tau$ is real number and $J$ means Bessel functions. How to do the asymptotic analysis when $\tau$ approaches zero? Any ...
2
votes
1answer
24 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$ ...
0
votes
1answer
55 views

What is the O-notation of $\prod_{i=1}^n \log i$ [closed]

Which rules of logarithms can help with evaluating $\prod_{i=1}^n \log i$?
0
votes
2answers
60 views

How would I show that $2^{n+2} + 3^{n+1}$ is $O(3^n)$ [closed]

Any help or hints would be appreciated.
3
votes
3answers
41 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: ...
6
votes
3answers
151 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
39 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
83 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
33 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
14 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 = ...
1
vote
0answers
27 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 ...
4
votes
7answers
437 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
35 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
47 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
15 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
0answers
28 views

How to study the asymptotic behavior of $f(r)=\int_0^1 dx\, \text{Li}_2\Big(1-\frac{r}{x(1-x)}\Big)$ for small $r$?

How does one study the asymptotic behavior of the integral $$f(r)=\int_0^1 dx\, \text{Li}_2\Big(1-\frac{r}{x(1-x)}\Big)$$ as $r\rightarrow0$ from positive values? Here $\text{Li}_2$ is the ...
0
votes
1answer
27 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
44 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
33 views

$f(n)=3f(\frac{n}{3})+O(logn)$

I was asked to figure out the time complexity analysis for the following recurrence relation: $f(n)=3f(\frac{n}{3})+O(logn)$ I worked it out as O(nlgn), Would like to know if this is right or ...
1
vote
0answers
16 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
31 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 ...
0
votes
1answer
23 views

Show a function similar to $(1/x)lnx$ becomes small as x grows

I am tasked with showing that, for $l \gg k$, $$ t = \frac{1}{l-k}\ln(l/k) $$ is small (it is given that $t$ is positive). Intuitively, this seems correct because it is 'similar' to $$ \frac{1}{x} ...
1
vote
0answers
44 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)} = ...
0
votes
0answers
12 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$, ...
1
vote
0answers
18 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 ...
2
votes
0answers
25 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 ...
4
votes
0answers
55 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
27 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
18 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
24 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
0answers
18 views

Non-deterministic multiplication algorithms

Are there any algorithms for non-deterministic Turing machines that can compute the decision problem $mn=x$ (where $m=O(n),x=O(n^2)$) faster than the equivalent deterministic algorithm? Equivalently, ...
0
votes
1answer
34 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
31 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
48 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}?$$