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

learn more… | top users | synonyms (1)

-2
votes
1answer
19 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 ...
3
votes
1answer
29 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 ...
1
vote
0answers
12 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
12 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
11 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
3
votes
1answer
41 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
1answer
29 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 ...
6
votes
1answer
381 views

Evaluating a limit of the truncated exponential series motivated by the prime number theorem for $k$ distinct prime factors.

If $\pi_k(n)$ is the cardinality of numbers with k factors (repetitions included) less than or equal n, the generalized Prime Number Theorem is: $$\pi_k(n)\sim \frac{n}{\ln n} \frac{(\ln \ln ...
3
votes
2answers
45 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 ...
1
vote
2answers
56 views

Efficiently calculating the 'prime-power sum' of a number.

Let $n$ be a positive integer with prime factorization $p_1^{e_1}p_2^{e_2}\cdots p_m^{e_m}$. Is there an 'efficient' way to calculate the sum $e_1+e_2+\cdots +e_m$? I could always run a brute ...
0
votes
2answers
26 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
vote
1answer
25 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 ...
1
vote
0answers
60 views

integral with respect to the point measure [on hold]

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$. ...
2
votes
2answers
53 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 ...
2
votes
3answers
71 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?
-1
votes
1answer
27 views

Big-O Math Problem [on hold]

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))$.
0
votes
1answer
69 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: ...
2
votes
1answer
19 views

Recursion and Time Complexity Concept

The question prompt is as follows: Consider the function $f(n)$ defined as: $$f(n) = \begin{cases}n(n-1)f(n-2) & n > 1\\1 & n=0,\; n=1\end{cases}$$ How may be $g(n)$ be defined ...
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 ...
4
votes
2answers
108 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$, ...
1
vote
1answer
27 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 ...
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
25 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 ...
0
votes
0answers
14 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
52 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 ...
-5
votes
0answers
21 views

What is the asymptote of the function? [on hold]

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
2
votes
0answers
78 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
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 ...
-1
votes
1answer
35 views

$t(n) = t(n-2) + 2^n$ [closed]

Assume that $t(n) = 1$ for $n\le 1$ and the recurrence given is for $n > 1$ $$t(n) = t(n-2) + 2^n$$ trying to find the recurrence within big theta accuracy, help!
2
votes
2answers
25 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 ...
0
votes
1answer
23 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{ ...
1
vote
0answers
25 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$ goes to infinity in the following situation: the ...
3
votes
2answers
2k views

Solve the Relation $T(n)=T(n/4)+T(3n/4)+n$

Solve the recurrence relation: $T(n)=T(n/4)+T(3n/4)+n$. Also, specify an asymptotic bound. Clearly $T(n)\in \Omega(n)$ because of the constant factor. The recursive nature hints at a possibly ...
0
votes
0answers
20 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(?)$$
5
votes
2answers
113 views

Asymptotics of $\int_{0}^{+\infty}\!\!\frac{dx}{\sinh^2(\epsilon \sqrt{x^2+1}) } $ for $\epsilon$ near $0$

How to find an asymptotic expansion, for $\epsilon$ near $0$, of the following integral $$ I(\epsilon):=\int_{0}^{+\infty}\frac 1{\sinh^2 (\epsilon \sqrt{x^2+1}) } {\rm d}x. $$ As $\epsilon ...
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
14 views

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? $$\{n\ |\ p(n)\ is\ prime\}$$ For example the density for $p(x)=x$ is zero and maybe in ...
1
vote
1answer
58 views

Which is the greatest integer value of $a$, for which $A'$ is asymptotically faster than $A$?

The recurrence relation $T(n)=7T\left( \frac{n}{2}\right)+n^2$ describes the execution time of an algorithm $A$. A "competitor" algorithm, let $A'$, has execution time $T'(n)=aT'\left( \frac{n}{4} ...
-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 ...
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 ...
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} ...
1
vote
1answer
53 views

If $f(n) = O(g(n))$ and $f(n) \not\in o(g(n))$, does $f(n) = \Theta(g(n))$?

If $f(n) = O(g(n))$ and $f(n) \not\in o(g(n))$, does $f(n) = \Theta(g(n))$? Well, this is just another algorithm's class HW question, but I don't seem to be able to figure out how to prove or ...
5
votes
1answer
42 views

Can $f(x+1) = f(x)^{\ln(x)}$ be expressed as integral transform $\int g(x,t) dt $?

Let $x$ be a real number. Can some real-analytic function $f$ that satisfies for $x>3$ :$f(x+1) = f(x)^{\ln(x)}$ be expressed by standard functions as an integral transform : $$f(x) = ...
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
1
vote
1answer
87 views

Asymptotic behaviour of a recurrence relation - How to solve

I'm going over a chapter in recurrence relations in preparation for job interviews and came across the following. I'd like to gain some better understanding of how to solve such a question. Find a ...
53
votes
1answer
1k views

Why are asymptotically one half of the integer compositions gap-free?

This is a longish post about something that has been haunting me for a while about a kind of restricted composition, namely gap-free and complete compositions. First, I will define the terms that are ...
1
vote
1answer
41 views

Can we deduce that $⌊r^{n}α⌋≃r^{n}α$ when $r→∞$?

Let $α∈(0,1)$ be an irrational number and let $n≥1$ be a fixed positive integer. For any $r>4$ we define the positive integer $$k=⌊r^{n}α⌋$$ where $⌊.⌋$ denotes the floor function. My question is: ...