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
2answers
29 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
0answers
12 views

Entropy of the Random Energy Model

I need to show that $$\text{lim}_{N \to \infty}\frac{1}{N}\text{log}\mathcal{N}(\epsilon, \epsilon + \delta) = \text{sup}_{x \in [\epsilon, \epsilon + \delta]}s_a(x).$$ We have that ...
0
votes
1answer
19 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
28 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
17 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
27 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
22 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
35 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
32 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
18 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
38 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
56 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
44 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
21 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 ...
-1
votes
1answer
28 views

Big-O Math Problem [closed]

I'm having trouble with a hard question, so, say 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))$.
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
69 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
30 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
58 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
16 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 ...
-5
votes
0answers
21 views

What is the asymptote of the function? [closed]

Find the horizontal or oblique asymptote of f(x) = (2x^2+5x+6)/(x+3) y=-3 y=2x-1 y=-5 y=-2x+5
3
votes
2answers
56 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
117 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
58 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
26 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$ ...
0
votes
0answers
37 views
+50

Density of primes in a polynomial

Consider that p(x) is a polynomial with integer coeficients. What is the natural density of the below set? $$A = \{n\ |\ p(n)\ is\ prime\}$$ and can we say an statement like prime number theorem ...
-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 ...
0
votes
1answer
40 views

How do I find the equivalence of the expression $e^{n\log(n)-(n+e)\log(n + e)}$?

We want to find equivalence of the expression $$e^{n\log(n)-(n+e)\log(n + e)}$$ Note that: $$\log(n+t)=\log\left[n\left(\frac{t}{n}+1\right)\right]=\log(n) + \frac{t}{n} ...
2
votes
3answers
93 views

$u_n=\exp( n\log n-(n+\epsilon)\log(n+\epsilon))$

how can i show this sequence $u_n$ is divergent: $$u_n=\exp( n\log n-(n+\epsilon)\log(n+\epsilon))\quad n\in \mathbb{N}^*;\quad \epsilon \in (0,1)$$ My attempts: \begin{align*} u_n&=\exp( n\log ...
1
vote
0answers
14 views

Is $f(n)=O(g(n))$ or $f(n)=\Omega(g(n))$ when $f(n) = (\log n)^{\log n}$ and $g(n) = n/\log n$?

I have showed that $f(n)=\Omega(g(n))$ in the following way. We assume that $${\log n}^{\log n} \leq n/\log n$$ $$\implies \log n \times \log \log n \leq \log n - \log \log ...
0
votes
0answers
19 views

If I colour n vertices independently, randomly with n^(1-x) colours, why is the size of the colour classes (1+o(1))n^x?

By o(1), I mean 'little-o' of 1. A paper I'm reading uses this result, but I can't see where it comes from. Thanks.