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

learn more… | top users | synonyms (1)

0
votes
2answers
15 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
22 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
0answers
28 views

How do you solve the following questions on asymptotic analysis. Please share your approach. [on hold]

Check this image: I have read about the three notations but I'm unable to use the concepts to solve questions like this.
0
votes
1answer
36 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 ...
0
votes
1answer
11 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
18 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
20 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: $...
0
votes
2answers
35 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
26 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 ...
1
vote
1answer
38 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}(...
3
votes
2answers
41 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 = ...
0
votes
2answers
41 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)+...
8
votes
3answers
262 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 ...
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
46 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
56 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
44 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\...
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.
8
votes
0answers
92 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
66 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} \...
1
vote
1answer
31 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-\...
0
votes
0answers
23 views

meromorphic function on torus

Consider the familly of meromorphic function on the square torus (endowed with the corresponding complex structure) with $p$ simple poles and $p$ simple zeros and $L^1$-norm equal to $1$ : $\mathcal ...
0
votes
3answers
37 views

Asymptotics of incomplete Beta function $B_{1/2}(y+1,y)$ when $y\to\infty$

My question concerns the behavior of the incomplete Beta function $$B_{1/2}(y+1,y)=\int_0^{1/2}x^y (1-x)^{y-1}dx$$ in the large $y$ limit. I have been looking everywhere, but I can't find anything. ...
0
votes
0answers
20 views

Determining bounds for a sum with nested infinite series

I am computing the inner product of the characters of the trivial and the $k$-th irreducible two dimensional representations of the dihedral group $D_n$ of order $2 n$ when $n$ is even. The ...
0
votes
0answers
22 views

Get an upper bound of $\left| F(1+it) \right|$ in an example of Perron type formula

From Proposition 3 of Tao, A cheap version of Halasz’s inequality, I know how get for example upper bounds for $x,T\geq 1$ $$\frac{1}{x}\sum_{n\leq x}\frac{\mu(n)\log n}{n}\ll\int_{-T}^{T} \left| \...
7
votes
1answer
666 views

Product of Fibonacci numbers

I'm looking for the asymptotic approximation of the product of the first $n$ Fibonacci numbers. Does there exist a tight approximation for these kind of things?
0
votes
1answer
20 views

An upper bound of $ \left| \frac{1}{s}\log\zeta(s) \right| $ for $\Re s=\sigma>1$, from this integral formula and a related comparison

For $\Re s=\sigma>1$ one has the following known formula $$\frac{1}{s}\log\zeta(s)=\int_1^\infty \Pi(x)x^{-s-1}dx,$$ then if we take the derivative we can write $$\frac{1}{s}\log\zeta(s)=s(s+1)\...
2
votes
0answers
25 views

How to find the asymptotic expansion of $\int_{-\infty}^{y} e^{-x^2/2}/\sqrt{2\pi} dx$ where $x \in N(0,1)$?

I realize the function inside the integral is the pdf of a normally distributed random variable x, but am unsure how to use this to solve the problem. I am trying to relate it to the inverse of the ...
1
vote
1answer
64 views

How to obtain $N_{\mu, i} (\lambda)=c_n \text{vol} (Q_i) \lambda^{\frac{n}{2}}+o(\lambda^{\frac{n}{2}})$? - Weyl's law

I am trying to prove the Weyl's asymptotic law for eigenvalues. In the document Weyl's law of p. $4$, I have managed to go up to the step $$\tilde{\nu_k} \leq \nu_k \leq \mu_k \leq \tilde{\mu}_k \...
1
vote
1answer
17 views

multiple of an integer and asymptotics

Let us suppose that we have a positive integer $N$. We take the integer $\lceil \log_2 N \rceil$. Does there always exist an integer $X \geq N$ such that the following both conditions are satisfied: ...
1
vote
1answer
50 views

When is $1-(1-p)^n \sim pn$

Let $0<p=p(n)<1$ with $p=o(1)$. For which $p$ is it true that $1-(1-p)^n \sim pn$? With $\sim$ I mean that they are asymptotically the same, so $\frac{1-(1-p)^n}{pn}\rightarrow 1$, or at least ...
3
votes
0answers
50 views

How quickly can we find a value that has large multiplicative order modulo $n$?

If we're trying to find an element modulo $n$ that has multiplicative order at least $\sqrt{n}$, how quickly can we do this? We don't know if $n$ is prime or composite, only that $n$ definitely has a ...
0
votes
2answers
37 views

$(x + y + xy)/2 = f( f^{[-1]}(x) + f^{[-1]}(y) )$

Consider $(x + y + xy)/2 = f( f^{[-1]}(x) + f^{[-1]}(y) )$ Where $f^{[-1}]$ denotes the functional inverse of $f$. How to find $f$ ? How about the more General idea of finding $f$ for a given $g$? ...
0
votes
2answers
54 views

Is there an way to calculate the value of O(n) [closed]

Is there an way to calculate the value of O(n) (Big Oh)? I understand it's use in algorithm. But my question is how is the value calculated?
-1
votes
1answer
31 views

Finding the Time Complexity in Big theta notation [closed]

sum = 0 ; for ( i = 0 ; i < n ; i++ ) for ( j = 1 ; j < n^4 ; j = 4*j ) sum++; How would I go about finding the time complexity in ...
2
votes
1answer
44 views

Could Master Theorem be applied to this recurrence relation?

I have the following recurrence relation $T(n) = 4T(\frac{n+4}{2}) + n$ Is there some way in order to apply the Master Theorem to it? Or do I have to find an alternative approach in order to solve ...
1
vote
0answers
33 views

Upper bounding a sum of products

Let $a_k$ be an integer valued sequence, $a_k \in \mathbb{N}^+$ and let $b_k = \#\{i: a_i=1,\; i \leq k\}$ and assume that $b_k=o(k)$ (little o notation). How to prove that there exists a constant $...
0
votes
0answers
23 views

Asymptotic behavior of inverse laplace transform [duplicate]

My question may be quite rough. Let $F(\lambda)$ be the Laplace transform of some function $f(t)$, $$ F(\lambda)= \int_0^\infty e^{-\lambda t}f(t) dt. $$ If I have knowledge about $F(\lambda)=O(\...
2
votes
1answer
37 views

Asymptotic lower bound of this function

Suppose that $n$ is an even number. Let $$f(n)=\frac{\sum_{j=1}^{n/2}\binom{n}{2j}\log(2j)}{2^{n-1}}.$$ Can we find some function $g(n)$ (e.g. $\log(n)$ or $n^\alpha$) such that $f(n)=\Omega(g(n))$? ...
2
votes
1answer
72 views

Finding 8 co-primes $\le 2^n$

We can find 8 co-prime integers $\le 2^n$ for sufficiently large $n$. I'm looking for asymptotic bounds for the minimum distance away from $2^n$ we have to go before finding 8 co-primes. In other ...
0
votes
1answer
22 views

asymptotic notations : if $0<a<b$ then $n^b=\Omega(n^a)$

If $0<a<b$ then $n^b=\Omega(n^a)$. I have learned about this quiet recently and have come across this equation. I am having difficulty proving this. Any help would be appreciated.
1
vote
2answers
73 views

Help with a limit using big O?

$\lim_{x\to 0} \frac{4sin^{2}(\frac{x}{2})-x^{2}cos(\frac{x}{2})}{4x^{2}sin^{2}(\frac{x}{2})}$ is equal to $\frac{1}{24}$ apparently but I can't work it out. My attempt: $\lim_{x\to 0} \frac{4(\frac{...
2
votes
1answer
56 views

Does satisfy $f(n)=\frac{\sigma(n)}{n^2}$ the hypothesis of Halasz’s inequality?

Let $\sigma(n)=\sum_{d\mid n}d$ the sum of divisor function. I would like to know if I can write an example of some of the following Theorem 1 or Theorem 2 from $$f(n)=\frac{\sigma(n)}{n^2}$$ in Tao, ...
0
votes
0answers
29 views

Combinatorics of classifying objects.

Given a multiset of $n$ primes (with product of multiset less than $2^{n\log n}$) how many ways can we assemble them into $k$ composite number of equal size? I am looking for asymptotics.
1
vote
2answers
61 views

Testing convergence of series $\sum_{n=1}^\infty\sin(\pi\sqrt{n^2+k^2})$ [duplicate]

Considering $$\sum_{n=1}^\infty\sin(\pi\sqrt{n^2+k^2})$$ depending on $k$, which can be real. I have absolutely no clue how to proceed. Tried to taylor it, but with no result.
1
vote
2answers
33 views

Correct order of the growth function [closed]

$5 \log( \log n) $ $n (\log n)^2$ $\sqrt{n} \log n$ $n^{\frac{4}{3}}$ $n \log (\log n)$ $7 \sqrt{n}$ What is the ascending order of the growth function? Please give the explanation as well.