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

learn more… | top users | synonyms (1)

1
vote
1answer
18 views

Showing $\limsup_{h \to {0}}\frac{O(h^2)}{h^2}<\infty$

Let $$y(h)=1-2\sin^{2}(2\pi h) , f(y)=\frac{2}{1+\sqrt(1-y^2)} $$ Justify the statement $$f(y(h))=2-4\sqrt{2}\pi+O(h^2)$$ where $$\limsup_{h \to {0}}\frac{O(h^2)}{h^2}<\infty$$
0
votes
1answer
23 views

Big-O of a Function

Given $F(N) = 55N(600 + 50N \log N + 20N) + 20N(30N + 20\sqrt N)(50 + \log N)$. How can one combine multiplication with addition for a Big-O estimate by algebraic means? I'm used to simply taking the ...
2
votes
0answers
10 views

Relationship between asymptotic distribution and logarithmic sums of elements of subset of the natural numbers

Consider a subset $A$ of the natural numbers analogous to the primes (but rarer). Let $a_n$ denote the $n$th element of $A$, and $a(n)$ denote the number of elements of $A$ less than or equal to $n$ ...
1
vote
2answers
24 views

Big $O$ — $3^n$ vs $n2^n$

I'm trying to compare $f(n) = 3^n$ and $g(n) = n2^n$ to determine whether $f \in O(g)$, $f \in \Omega(g)$, or $f \in \Theta(g)$. My gut is telling me that $g(n) = n2^n$ grows faster, and so $f \in ...
1
vote
1answer
51 views

Proof $(\log(n))^{\log(\log(n))} = O(n)$

Can someone provide a proof that $(\log(n))^{\log(\log(n))} = O(n)$? Preferably without calculus, but I'll take what I can get. Just ran into this problem, and I have no way of moving forward, ...
2
votes
1answer
38 views

What is the point of big Oh notation when it is used for estimation?

I'm reading a book on number theory at the moment that assumes familiarity with big Oh notation...and while I think I do understand the notation I cannot understand the point of it. For instance let ...
0
votes
0answers
9 views

How to solve this kind of difference equation?

How to find $v_k$, $k=0,1,2,\dots$ such that $$v_k + \sum_{n=1}^{k} \frac{\alpha^n}{n}v_{k-n} + \sum_{n=1}^{k}\frac{\beta^n}{n}v_{k+n} = 0,$$ where $\alpha,\beta \in \mathbb{C}$. ($v_i=0$ for ...
1
vote
2answers
34 views

Is $\lceil{\lg n}\rceil!$ polynomially bounded?

Is $\lceil{\lg n}\rceil!$ polynomially bounded? I've tried using Stirlings Approximation, and I get that $\lceil{\lg n}\rceil! \approx \sqrt{2\pi}\lceil{\lg n}\rceil^{1/2}\lceil{\lg n}\rceil^{\lceil ...
0
votes
1answer
21 views

Big Omega problem : is $n^2\in\Omega (2n^2)$?

Is $n^2\in\Omega (2n^2)$? If we find the limit we can see $\frac{1}{2}>0$, which means it is true, but I haven't learned the limit method. I need to figure out using this definition $\exists ...
2
votes
1answer
29 views

Asymptotic formula for sums related to primes

Suppose $0 < \alpha < 1$. What is the asymptotic formula for the sum $$\displaystyle \sum_{p \leq x} \frac{\log p}{p^\alpha}?$$ Thanks for any insights.
0
votes
1answer
20 views

summation inequality with logarithms

show: $$\sum_{i=1}^n \log_{2}\,i = O(n\log n)$$ Proof by induction: $$\sum_{i=1}^n \log\,i \le n\log n$$ $$\text{Test for n=1: }\sum_{i=1}^1 \log_{2}\,i \le 1\log 1$$ $$0 \le 0\text{ true for ...
1
vote
1answer
18 views

Determine whether each pair is $f(n) = O(g(n), f(n) = \Omega(g(n)), or f(n) = \Theta(g(n)).$

For the pair of functions, find whether it's $f(n) = O(g(n), f(n) = \Omega(g(n)), or f(n) = \Theta(g(n)):$ $a) f(n) = 12^n , g(n) = 7^n$ $b) f(n) = log_9(n^4), g(n) = log_9(n^5)$ I understand that: ...
0
votes
1answer
10 views

Need explanation on asymptotic running time results for various functions

I did not understand few results from the book problem. Here is the problem: Indicate, for each pair of expressions (A, B) in the table below, whether A is O, o, Ω, ω, Θ of B. Assume that k ≥ 1,  > ...
0
votes
2answers
30 views

proof by induction summation inequality

show by induction that: $$\sum_{i=1}^n i^2 = O(n^3)$$ what I have so far: $$\sum_{i=1}^n i^2 <= n^3$$ base case: for n=1 $$\sum_{i=1}^1 i^2 <= 1^3$$ ...
0
votes
0answers
23 views

Let g and h be any functions from naturals to (0,infinity)

Let $g$ and $h$ be any functions $\mathbb{N} \to (0,\infty)$. Then $g(n) \in \Omega(h(n))$ implies there is some $N \in \mathbb{N}$ such that $g(n)\ge h(n)$ for all $n \ge N$. Picture of question : ...
0
votes
0answers
8 views

Am I comparing big-O runtime correctly?

I'm working on some homework regarding runtimes and Big-O notation. I've struggled with this for quite some time, but I think its slowly making more sense. If someone could verify that I'm doing these ...
2
votes
1answer
38 views

Higher Order Terms in Stirling's Approximation

Some websites and books give stirling approximation as $$n! = \sqrt{2 \pi n} \left( \frac{n}{e} \right)^n \left( 1 + O \left(\frac{1}{n} \right)\right)$$ However when I check their derivations most ...
-3
votes
1answer
28 views

If $f(n)$ is not $\Theta (g(n))$ does it follow that $\log f(n)$ is not $\Theta(\log g(n))$?

If $f(n)$ is not $\Theta (g(n))$ does it follow that $\log f(n)$ is not $\Theta(\log g(n))$? We say that $f(n)= \Theta (g(n))$ if there exist some constants $c_1$ and $c_2>0$ and $n_0$, such ...
2
votes
1answer
42 views

Asymptotics of $\sum_{\mathfrak{a}}\frac{n^{k-\epsilon}}{\mathfrak{N}\left(\mathfrak{a}\right)^{r\left(k-\epsilon\right)}}$

In this paper by Brian D. Sittinger, the following claim is made: For an algebraic number field $K$ with norm $\mathfrak{N}$, let $\epsilon=\left[K:\mathbb{Q}\right]^{-1}$. Then, taking the sum over ...
1
vote
0answers
20 views

Compute the asymptotic expansion of the integral by Watson's Lemma

Use Watson's Lemma to find the asymptotic expansion of the following integral as $\lambda \to \infty$ with $\lambda>0.$ Assuming that $\phi (t)$ is infinitely differentiable on $[0,1].$ ...
1
vote
0answers
12 views

Calculating Upper bound of a function [duplicate]

If T(N) = T(sqrt(N)) + 1 and T(1) = 1 then what is the upper bound i.e O(N) for this function? sqrt(N) => square root of N
2
votes
1answer
40 views

Asymptotics of $\sum_{n\leq x}\tau_{k}\left(n\right)$

We define $\tau_{k}\left(n\right)$ to be the number of ordered $k$-tuples of positive integers with product equal to $n$. It is easily shown that this satisfies the recurrence relation ...
3
votes
2answers
58 views

Prove that $7n^2 + 2n + 3 = O(n^2)$ using the definition of O notation.

Prove that $7n^2 + 2n + 3 = O(n^2)$ using the definition of O notation. I need to use two constants and prove that they satisfy the O definition. I'm new to big O and want to know whether I am ...
3
votes
1answer
45 views

What proportion of the positive integers satisfy this number-theoretic inequality?

Let $\sigma(x)$ be the sum of the divisors of the positive integer $x$, and let the abundancy index of $x$ be defined as $$I(x) = \frac{\sigma(x)}{x}.$$ My question is this: What proportion of the ...
2
votes
2answers
24 views

Determining order class of $T(n) = nT(n-1) + n$ with $T(1) = 1$

I'm trying to solve the following problem: Define $T(n) = n\cdot T(n-1) + n$ with $T(1) = 1$. Is $T(n) \in \mathcal O(2^n)$? I started by finding the time complexity of $T(n) = n\cdot T(n-1) + ...
1
vote
1answer
26 views

Series involving primes

Trying to find an asymptotic bound for the series $$ S(x) =\sum_{p\leq x}\frac{\varphi(p-1)}{(p-1)p} $$ as $x \rightarrow \infty$. Of course $$ \frac{\varphi(p-1)}{p-1} =\prod_{q\mid ...
0
votes
2answers
27 views

Big-O math Question

I'm having trouble with this question: Suppose that $f(x), g(x)$ and $h(x)$ are functions such that $f(x)$ is $O(g(x))$ and $g(x)$ is $O(h(x))$. Prove that $f(x)$ is $O(h(x))$. I have tried ...
2
votes
3answers
75 views

Proving with Big O Notations

Is there a way I can prove that $O(3^{2n})$ does NOT equal $10^n$? How would that be done? Also, is it okay to simplify $O(3^{2n})$ to $O(9^n)$ to do so?
0
votes
1answer
73 views

Big O Proof by Contradiction

Question: Use a proof by contradiction to show that $5^n$ is not $O(3^n)$ NOTE: This is homework, please don't provide an answer, just want to know if I am on the right track. My Attempt: ...
1
vote
2answers
19 views

Understanding the logic behind this summation

The following is an excerpt from a proof that $\sum_1^n {i^k} = \theta(n^{k+1})$: $$\sum_1^n{i^k} \ge \sum_{\lceil n/2 \rceil}^n{i^k} \ge \sum_{\lceil n/2 \rceil}^n{\lceil n/2\rceil^k}$$ The first ...
1
vote
1answer
28 views

Showing $n^{\log{n}} = o(2^n)$

I would like to show that $n^{log n} = o(2^n)$. Here is my attempt: I see that $\log{(n^{\log{n}})} = (\log{n})^2,$ and $\log{2^n} = n\log{2}$. I also know that $(\log{n})^2=o(n)$, so that for ...
1
vote
0answers
73 views

integral with respect to the point measure [closed]

We have integral $$\int_0^tf(t-u)dX(u)$$ where $X(u)$ is random point process( or at least renewal process). Also it is known that $f(t)\sim t^{-\alpha},$ $0<\alpha<1$ as $t\rightarrow \infty$. ...
0
votes
1answer
9 views

Orders of Asymptotes

We know that $\log(X)^n = o(X^\epsilon)$ for all $n,\epsilon>0$. My questions is, is $\log(X)$ the largest function that is smaller than all (small) powers of $X$. That is, can we find a ...
1
vote
2answers
31 views

On finding the order of an infinitely small quantity

Given an infinitely small quantity: $$\alpha \left ( x \right )= \tan \left ( x \right )-\sin \left( x \right)$$ as x aproaches $0$, and computing the corresponding asymptotic relationship. What does ...
3
votes
2answers
59 views

Can we give a bound on any associative function?

We say that $f:[1,\infty)^2\to[1,\infty)$ is associative if $$f(f(a,b),c)=f(a,f(b,c))$$ And symmetric if $$f(a,b)=f(b,a)$$ e.g. the arithmetic operations '+' and '$\cdot$' are associative and ...
2
votes
2answers
54 views

How do I show that as $z \to \infty$ that $\int_0^\infty \frac{t - \lfloor t \rfloor - 1/2}{z + t} dt = O(z^{-1} )$??

How do I show that as $z \to \infty$ that $\int_0^\infty \frac{t - \lfloor t \rfloor - 1/2}{z + t} dt = O(z^{-1} )$? According to Serge Lang, the integral on the left is the error term for Stirling's ...
0
votes
0answers
17 views

Trying to understand Ωlog(n!) ∈ Ω(n log(n))

So I'm trying to understand the proof of Ωlog(n!) ∈ Ω(n log(n)) but I'm lost. Here's what I understand up to: log(n!) ≧ log(n ∙ (n−1) ∙ (n−2) ∙ … ∙ 3 ∙ 2 ∙1) <-- This makes sense. Showing a log ...
3
votes
2answers
58 views

Asymptotic form of an integral

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 ...
4
votes
2answers
119 views

Closed form for $ \prod_{k=1}^n (a+k^2) $

I have come across the following product: $$ \prod_{k=1}^n (a+k^2) $$ where $a$ is a positive constant. Could anyone suggest a closed form for this product? I need to approximate this for large $n$, ...
2
votes
2answers
32 views

Asymptotic expansion of the complete elliptic integral of the first kind

The complete elliptic integral of the first kind is defined as $$K(k) = \int_0^{\pi/2} \frac{d x}{\sqrt{1 - k^2 \sin^2 x}}.$$ I would like to derive (at least the first term of) the asymptotic ...
2
votes
0answers
83 views

$f(x)\sim 1/x \implies (1+f(x))^x\to e$, but what family of functions maximizes the speed of convergence from below?

This problem is subordinate to finding out if $$\left(1+\frac{\log p_{n+1}}{p_n}\right)^{p_{n+1}/\log p_n},$$where $p_n$ is the $n$-th prime, never stabilizes above or below its limiting value, which ...
0
votes
1answer
26 views

Multiplication of two asymptotic expansions

I have two functions $g, f:(0,\infty)\rightarrow \mathbb{R}$ with asymptotic power series as follows: For all $N\in\mathbb{N}:$ $$f(t) \sim \sum\limits_{n=0}^{N} a_n t^n + O(t^{N+1}) \text{ }\text{ ...
0
votes
1answer
59 views

Prove $\lim_{n \to \infty}$ $(1+\frac xn-o(\frac 1n))^n=e^x$ [duplicate]

We know that $\lim_{n \to \infty}$ $(1+\frac xn)^n=e^x$. How to prove that $\lim_{n \to \infty}$ $(1+\frac xn-o(\frac 1n))^n=e^x$? Attempt of the proof: Let $\epsilon>0$ $\exists n_0$ such that ...
2
votes
0answers
33 views

Method of stationary phase for double integrals

I am looking for a reference for the leading term in the asymptotics of a double integral over a finite rectangle R of $K(x,y)\exp(i \,t\, h(x,y))$ as $t \to \infty$ in the following situation: the ...
0
votes
1answer
27 views

Weyl's law, meaning of the asymptotic formula, does it imply a bound?

Weyl's law states the eigenvalues of the Laplacian behave as $$\lambda_j \sim f(n)j^{\frac 2n}\quad\text{as $j \to \infty$}$$ where $n$ is the dimension. Does this literally mean that, $$\lim_{j \to ...
2
votes
2answers
25 views

How to bound the tail of p-series

How can I asses $S_n = \sum_{j=n}^\infty\frac{1}{j^p}, p>1$ in terms of $n$, specifically can I get something like $$S_n = O(?)$$
0
votes
0answers
14 views

an oscillatory integral with two parameters

Consider $$I(a,b)=\int_{\mathbb{R}}e^{i(ax^2+bx)}\psi(x)\,dx$$ where $\psi$ is smooth and supported in $\{x:|x|\in[1/2,2]\}$. How to control $I(a,b)$ in terms of $a$ and $b$? Moreover, is there an ...
1
vote
2answers
23 views

How to prove $\omega$ bound without using limit?

How to show $n^{3.4} - 2015n^{2} + 3$ $\in$ $\omega(n^{3})$ without using limit? According to the definition of $\omega$, $f(n)$ $\in$ $\omega(g(n))$ if and only if $\forall c > 0$, $\exists n_0$ ...
1
vote
1answer
75 views
+50

Density of primes in a polynomial

Consider that $p(x)$ is an irreducible polynomial with integer coeficients, that $\mathrm{gcd}$ of its coefficients is $1$. What is the natural density of the below set? $$A = \{n\ |\ p(n)\ \text{is ...
-1
votes
3answers
33 views

The curve $x^3-y^3=1$ is asymptotic t the line $x=y$. Find the point n the curve farthest from the line $x=y$. [duplicate]

The curve $x^3-y^3=1$ is asymptotic t the line $x=y$. Find the point in the curve farthest from the line $x=y$ This is just need of further details in this ...