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
2answers
558 views

Big O Notation / landau symbols

I want to write these two in the big O notation: (it's $h\rightarrow0$) $f(h)=\sqrt{h^3}$ $f(h)=h\cdot \log h $ But I don't have any idea how to do this. Thanks for helping!
0
votes
1answer
401 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
2answers
38 views

what is asymptotic behavior of $\sum \frac {1}{\sqrt[\alpha] k}$ [duplicate]

Asymptotic behavior of $$\sum \frac {1}{\sqrt[\alpha] k}$$ for $\alpha=1$? is $\ln k$ what about $\alpha > 1$ ? the suggested link is for $\alpha > \frac{1}{2}$ my question is about $ 0< \...
1
vote
0answers
38 views

On relationships between the general terms of sequences from different equivalences to the Riemann Hypothesis

The following are simple deductions using easy calculations for inequalities and limits. I define the following sequences, whose shape is inspired in Nicolas, Robin and Lagarias, respectively, ...
0
votes
0answers
13 views

Asymptotics of ratio of confluent hypergeometric functions of the second kind.

How can I show that $\frac{U(1-d,1,-1)}{U(-d,1,-1)}=-\frac{1}{d}+\frac{1}{d^{3/2}}-\frac{3}{4d^2}+O\left(\frac{1}{d^{5/2}}\right)$. Where $U(a,b,x)$ denotes the confluent hypergeometric function of ...
0
votes
1answer
406 views

Asymptotic distribution of MLE of geometric distribution

I need to find the asymptotic distribution of the MLE of a geometric distribution. I know $\overline X$ goes as $N(1/p, (1-p)/(n p^2))$. Using the delta method MLE=$1/\overline X$ goes as $N(p, (1-p)/(...
2
votes
1answer
75 views

Density of Pythagorean triples

We define a Pythagorean triple as a triple $<a,b,c>$ such that $a,b,c\in \mathbb N$ and $a^2+b^2=c^2$. In order to avoid duplicates, we say that a triple $<a,b,c>$ is legit iff $b>a$. ...
0
votes
1answer
45 views

Finding the product of a prime function…

If we take the primes $p_k < n$, and raise them to the highest power possible such that $(p_k)^{r_k} \le n$, what is the lower bounds on $\prod{ (p_k)^{r_k} }$? In other words, what are the ...
3
votes
0answers
30 views

Asymptotic behavior of a function defined via a complex integral

I would appreciate any comment/correction about what I did for the following problem, I would be very thankful if you let me know the parts of it which may not be very precise: Let $g(z)$ be defined ...
0
votes
0answers
14 views

Asymptotic Expansions of a Generalized Hyper-Geometric Function

Let $t>0,x>0$, and $$\{a_1,a_2,a_3\}=\{2, 2, 9/8 - (i t)/2\}$$ $$\{b_1,b_2,b_3,b_4\}=\{1, 1, 3/2, 17/8 - (i t)/2\}$$ We are looking for the asymptotic expansions of a generalized hyper-...
0
votes
1answer
28 views

An asymptotic numeric problem.

Given a large enough integer $N$ is there always a $c\in(0,1)$ such that $$(N+ N^{1-c}){c\ln(e N)}>\ln( N+( N)^{1-c})(N+2 N^c)$$ holds? What is this $c$ explicitly (at least a close approximation ...
0
votes
0answers
37 views

Asymptotics of Inverse Laplace transform of a function with a branch point and singularities

consider the inverse Laplace transform $f(x)=L^{-1}[\tilde{f}]$ of a function $\tilde{f}(s)$. I would really like to find the large-$x$ asymptotics of $f(x)$ for the following case: $$\tilde{f}(s)=\...
0
votes
0answers
20 views

An asymptotic growth problem.

Given a function $f:\Bbb N\rightarrow\Bbb N$ what is the largest growing function $g:\Bbb N\rightarrow\Bbb N$ we can take such that $$\Bigg(1-\bigg(1-\frac1{f(n)}\bigg)^{\binom{g(n)}{h(n)}}\Bigg)^{\...
1
vote
1answer
28 views

Solving recurrence relations to find asymptotic behavior

My goal is to solve the following recurrence relation so that I can find the asymptotic behavior of T(n): T(n) = 5T(n/3) + n. I've been able to almost solve but I'm just stuck in one particular step. $...
0
votes
0answers
34 views

Is it possible to compute this series?

Question Given: $$ a_r = \sum_{ mn=r} \mu(m) c_n$$ where $\mu(m)$ is the mobius function. And $$c_n= n^s$$ Is there any asymptotic/direct method to compute the below? $$\sum_{r=1}^\infty \frac{...
0
votes
0answers
11 views

Is a circular restriction possible (will elaborate)

When making rational functions, you may get various kinds of restrictions (as the difference in power increase the difference is the shape of restriction) so if by stating an implicit function that ...
3
votes
1answer
56 views

Asymptotic vlaue of $ f(n)=\sum_{i=0}^n\lfloor \sqrt{i}\rfloor\binom{n}{i} $

Inspired by this question I tried to find an asymptotic formula for $$ f(n)=\sum_{i=0}^n\lfloor \sqrt{i}\rfloor\binom{n}{i} $$ With the observation: $$ f(n)=\sum_{i=0}^n\frac{\lfloor \sqrt{i}\rfloor+\...
0
votes
2answers
91 views

Prove that $\log(n!)\leq(\log(n))!$

Prove that $\log(n!)\leq(\log(n))!$ My attempt: I read somewhere that $n\leq\log(n!)\leq(\log(n))!$. But when I used calculator $\log(n!)$ can not be less than or equal to $(\log(n))!$. ...
3
votes
1answer
97 views

Does $a_n \sim b_n$ imply $\sum_n a_n \sim \sum_n b_n$ for $a_n, b_n>0$?

I am almost embarrassed to asked to this question, but after considering it for a while I realize I need some help. In the following $a_n, b_n >0$. So, by limit comparison test if $a_n = O(b(n))$ ...
0
votes
2answers
12 views

Asymptotic Analysis of same-degree functions

On a recent test, I was asked whether the following is true or false: True or False: $10n^3 = O \left( 0.42n^3 \right)$ Comparing the two functions as n approaches infinity, I get: $ \lim_{n \...
10
votes
3answers
281 views

Asymptotic behaviour of sum over the inverse japanese symbol

I am interested in the asymptotic behavior of the sum $$\sum_{m=1}^M\frac{1}{\sqrt{m^2+\omega}}$$ for $1>\omega>0$ in the Limit $M\to\infty$ up to order $\mathcal{O}(M^{-1})$. The first thing I ...
0
votes
0answers
25 views

“Solving” for a sequence given an (expected) expression for the summation

Consider the "equation" \begin{equation} \frac{1}{a_n}\sum_{k=1}^n ka_k = \mathcal{O}\left(\frac{n^2}{\log n}\right).\tag{1}\label{eq:conjec} \end{equation} Does there exist some monotonically ...
1
vote
2answers
29 views

Growth function and one misunderstanding point?!

I have a question about Growth and Asymptotic notation topic. My question is as follows: $2^n$ > $n^{log_2{(n)}}$ is True. anyone could say how we can deduce that this fact is true?
0
votes
1answer
24 views

Big O notation for summation function

May be I am missing something very simple but I am finding it hard to understand why Big O for summation is O(n^2). I know that Big O for summation comes from fact that sum(1 to n) = n(n+1)/2. But if ...
0
votes
1answer
37 views

Would these witnesses satisfy this big-O function?

I'm trying to determine if $f(x) = \lceil x/2 \rceil$ is $O(x)$. I know that this is true, and the textbook answer is: $|\lceil x/2\rceil|\leq |(x/2)+1| \leq C|x|$ for all $x > 2$, with ...
1
vote
2answers
207 views

Does $f(\epsilon)=o(\epsilon\ln(\epsilon))$ imply $\frac{f(\epsilon)}{\epsilon}=o(1)$?

I have the following homework question: Does $f(\epsilon)=o(\epsilon\ln(\epsilon))$ imply $\frac{f(\epsilon)}{\epsilon}=o(1)$ ? It doesn't seem correct to me, using the definition I could only ...
0
votes
1answer
13 views

Summation with Floor and Square Root functions + Tight Bounds

I was applying a methodology that allows to come up with iterative algorithms time-complexity function's closed-form. I ran into a particular where I ended up with the result below. I wouldn't have ...
0
votes
1answer
25 views

Necessary and/or sufficient conditions for summability of a sequence

It is clearly true that any $(a_n)_{n=1}^\infty$ that has $$a_n=O(n^{-1-\varepsilon}),$$ for some fixed $\varepsilon>0$, is absolutely summable: $$\sum\limits_{n=1}^\infty |a_n|<\infty.$$ My ...
0
votes
0answers
22 views

numerical integration asymptotic relation

Let $Q\subset R^n$ be a convex subset and $f\in C^2(Q)\;$ We set $x_s:=\int_Q xdx$,$\;\;\;Vol(Q):=\int_Q 1dx$ and $diam(Q)=sup||x-y||_2$ Prove the following asymptotic relationship: $...
12
votes
4answers
239 views

An equivalent for $\sum_{n=0}^{\infty} e^{-x\sqrt{n}}$ as $x$ tends to $0^+$

I would like to obtain an equivalent form for $$ f(x)=\sum_{n=0}^{\infty} e^{-x\sqrt{n}} $$ as $x \rightarrow 0^+$. I tried without success to "remove" the $\sqrt{\cdot}$ in the summand by summing ...
0
votes
2answers
36 views

Difference between the definitions regarding distribution of prime numbers

Following are the two theorems that Hardy and Wright state in their book Theorem A: The number of primes not exceeding $x$ is given by $\pi(x) \sim \frac{x}{\log{x}}$. Theorem B: The order ...
-1
votes
2answers
40 views

Solve $\sqrt{1-2x+x^2+o(x^3)}$ with $x \to 0$ [duplicate]

I need help to solve $\sqrt{1-2x+x^2+o(x^3)}$ with $x \to 0$, I do not understand when and why I should stop. Here my steps: I can use Taylor formula for $\sqrt{1+t}$ so: $$\sqrt{1+t} = 1+ \frac{t}{...
1
vote
0answers
30 views

The asymptotic behaviour of $\sum_{1\leq k\leq N-1}\int_{p_k}^{p_{k+1}}\log x d[x]$, where $p_n$ is the nth prime number

Let $p_k$ is the kth prime number and consider for $N\geq 2$ the arithmetic function $$f(N)=\sum_{k=1}^{N-1}\int_{p_k}^{p_{k+1}}\log(x) d[x]$$ where $[x]$ is the integer part function (provide us in ...
3
votes
2answers
43 views

Estimate growth of a recurrence convolution

Consider the following recurrence relation $$ a_{m+1} = (4 m + 1) \sum_{k=1}^m a_k a_{m-k+1}, \qquad a_1 = 1. $$ The first several values are $$ a_1 = 1,\; a_2 = 5,\; a_3 = 90, \; a_4 = 2665, \; a_5 = ...
1
vote
1answer
40 views

Why is the CLT stated like it is?

The CLT says that given finite variance of iid RVs, we have $$\sqrt{n}( \bar{X} - \mu) \rightarrow \mathcal{N}(0,\sigma^2),$$ but if this is true, then $\bar{X} - \mu$ should converge to $\mathcal{N}(...
8
votes
0answers
95 views

Generalizing the growth of sums of two squares

Consider the set $S$ of numbers which are the sum of two (integer) squares, and define $S(n)$ as the number of members of $S$ in $\{1,2,\ldots,n\}.$ It is well-known that $$ S(n) \sim \frac{Kn}{\sqrt{\...
0
votes
2answers
43 views

Proving $f(n)=100n+5 \neq \Omega(n^2)$

I have to prove that: $$f(n)=100n+5 \neq \Omega(n^2)$$ What I tried: let's assume that $f(n)=100(n)+5= \Omega(n^2)$. Thus, there must exist some positive constant $c$ and $n_0$ such that, $$0 \leq ...
1
vote
1answer
40 views

How many polynomials are squarefree?

Of course, this depends on the field, and how we measure "how many," but it seems I cannot find an answer to this except over finite fields. My question specifically is If we have a field $F = \...
0
votes
3answers
46 views

How do I find Big O notation for this function?

How do I find Big O notation for this function? $$ n^4+100\cdot(n^2)+50 $$ In the book I am following, I got the following solution: $n^4+100(n^2)+50 \leq 2(n^4) \ \forall \ n \geq 11$ $n^4+100(n^2)+...
1
vote
1answer
54 views

For any arithmetic progression $n \in \Bbb{N} : n \equiv b \pmod a$, the natural density is $\frac{1}{a}$?

This question comes from here (page 10). Given that $d(A) := \lim_{x\to\infty}\frac{1}{x}\sharp\{n \leq x : n \in A\}$, how do I get that: $d(n \equiv b \pmod a) = \lim_{x\to\infty}(\left [ \frac{x}...
6
votes
1answer
844 views

Can a curve be an asymptote?

$f(x)=x^3+\frac{3}{x-1}$ This was the question given to me. I replied that $f(x)$ will have only a single vertical asymptote of $x=1$. My teacher told that there'll be be two asymptotes. One is the ...
1
vote
0answers
23 views

Finding a degree-2 polynomial that sits under the Harmonic Numbers.

Does there exist a degree-2 polynomial with positive acceleration such that the real extension of the harmonic numbers surpasses it for all future values? This was too big of a title and it's a ...
2
votes
2answers
47 views

How to solve asymptotic expansion: $\sqrt{1-2x+x^2+o(x^3)}$

Determinate the best asymptotic expansion for $x \to 0$ for: $$\sqrt{1-2x+x^2+o(x^3)}$$ How should I procede? In other exercise I never had the $o(x^3)$ in the equation but was the maximum order to ...
0
votes
0answers
64 views

How much can the integrability at zero tell about the decay rate around zero?

Suppose that $g$ is a continuous, nonincreasing and nonnegative function on $(0,1)$. The question is whether one can characterize the integrability of such functions at zero by their decay rates at ...
1
vote
0answers
45 views

Questions Concerning “Approximate Polynomials”

In this paper, I encountered the following definition: Definition 2 (Approximate Polynomial) Let $U\subset \mathbb{C}$ and $\sigma\in\mathbb{N}\cup\{-\infty\}$. A function $f\colon U\to\...
5
votes
3answers
335 views

Asymptotics for partitions of $n$ with largest part at most $k$ (or into at most $k$ parts)

Let $\bar p_k(n)$ be the number of partitions of $n$ with largest part at most $k$ (equivalently, into at most $k$ parts). Is there an elementary formula for the asymptotic behavior of $\bar p_k(n)$ ...
0
votes
3answers
21 views

Proving that $h=O(\log_2 n)$ if $h=\log_2 (n+1)$

Suppose that $h=\log_2 (n+1)$. Why is $h$ also $O(\log_2 n)$? I know the definition of big $O$ notation, and properties or logarithms, but I can't figure it out - that $+1$ is causing troubles.
1
vote
1answer
32 views

Probability that at least 2 edges of $\Gamma_{n,N}$ shall have a point in common

In the classic paper of Erdos,Renyi On the evolution of random graphs[page 7] ,it is argued that the probability that at least 2 edges of $\Gamma_{n,N}$ shall have a point in common is given by $1-\...
1
vote
0answers
109 views

What is $\int_{\Omega'} \psi (\nabla p) dV \: \text{as} \: \delta\alpha \rightarrow 0$?

I have an axi-symmetric integral (the domain and all functions are axi-symmetric) in cylindrical coordinates which needs to be integrated by parts for use in a finite element code. The integral is ...
0
votes
2answers
67 views

Theorem 3.16. in Analytic Number Theory by Apostol

The below texts are from the book Introduction to Analytic Number Theory by Apostol: I have two questions which I couldn't find solutions for them: $1-$ According to Thm 3.16., $\sum_{n\le x} \...