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
0answers
17 views

What about $\sum_{\substack{2\leq n\leq y,\text{n prime}}}n\log\log n$ when $y=[x]\to\infty$?

For a real $x\geq 2$ and when we take $y= [x]$ its integer part, I am trying to study the asymptotic size or growth of $$\sum_{\substack{2\leq n\leq y,\text{n prime}}}n\log\log n,$$ I believe that ...
0
votes
1answer
10 views

How to get values of $n_0$ and $c$ for big-omega.

Let $f(n)=3n^3$ and $g(n) = n^3$ then $f = Ω(g)$ Answer: Let $n_0 = 0$ and $c = 1$ So I know how to find $c$ and $n_0$ for big-oh, like this: $3n^3 \leq cn^3$ [divide to be left with c] $= c ...
1
vote
0answers
25 views

Approximating $\prod_{r=s}^t (1-b/r)$

I am currently trying to place an order of precision on the approximation $$\prod_{r=s}^t \left(1-\frac{b}{r}\right) \approx \left(\frac{s}{t}\right)^b$$ This follows because $$\prod_{r=s}^t ...
0
votes
0answers
10 views

Derive the asymptotic distribution of $\frac{2}{n(n-1)}\sum\sum_{i<j}|X_{i}-X_{j}|$

Derive the asymptotic distribution of Gini's mean diference, which is defined as $\frac{2}{n(n-1)}\sum\sum_{i<j}|X_{i}-X_{j}|$. This is an exercise of Asyptotic Statistics by A.W. van der Vaart. I ...
1
vote
0answers
27 views

Asymptotic sums and big-O notation

Suppose I have to compute the following asymptotic sum ($x\rightarrow\infty$): $$ S(x):=\sum_{n\leq f(x)} O(g(x,n))\;, $$ where the function $g(x,n)$ is non-decreasing in $n$, so that in our case ...
0
votes
0answers
8 views

mann's test for trend

To test the null hypothesis that a sample $X_{1},...,X_{n}$ is i.i.d. against the alternative hypothesis that the distributions of the $X_{i}$ are stochastically increasing in $i$. Mann suggested to ...
0
votes
0answers
5 views

Getting the shape (or bounding tail estimates) of a probability distribution from its generating function

Consider "random strings" over an $m$-letter alphabet where we are looking for the first occurrence of $k$ consecutive identical digits. I was with some effort able to find that the random variable ...
0
votes
1answer
15 views

Find the asymptotic solution $\Theta$ of the recurrence using the master theorem

I just took a quiz for an algorithms class that I didn't do so well on. It was on the master theorem. Unfortunately the professor refuses to supply answers or even tell me what I got wrong, so I was ...
2
votes
2answers
15 views

Comparing the growth of two function by taking logarithms

I was trying to understand how to compare the big-O growth of two functions by taking the logarithm (or some increasing function like $\sqrt{f(n)}$. For example, take $2^{({log_2n})^2}$ vs $ ...
0
votes
0answers
23 views

Growth rate of $\zeta(n)^{-1}$

What is the asymptotic growth rate of $\frac1{\zeta(n)}$? Is it polynomial in $n$?
0
votes
2answers
41 views

Prove or disprove that $\forall n \in N$ $, \, n! \in \mathcal{O}(2^n)$

Prove or disprove that $\forall n \in N$ $, \, n! \in \mathcal{O}(2^n)$ My attempt: $f(n) = n!$ $g(n) = 2^n$ First I checked if I needed to prove or disprove this statement, and to do so I ...
2
votes
1answer
43 views

Master method and choosing $\epsilon$

I am reading CLRS3, currently Chapter 4 and Section 4.5, "The master method for solving recurrences." I understood what is the $\epsilon$ , but I can't understand why they choose $ \epsilon ...
-1
votes
1answer
22 views

Asymptotic analysis : Theory

how do you prove that when the limit of n approaches towards positive infinity while n^2/(log n)! We tried to used Stirling theorem but this may not work due to the fact that it may or may not exist ...
0
votes
0answers
25 views

Asymptotic behavior of two functions

I have trouble figuring out the asymptotic behavior of two functions. If $f(n) = n \log n$, then what do we know about $f^{-1}(n)$? I.e. what is the asymptotic behavior of $g(n)$ such that $g(n) ...
0
votes
1answer
24 views

Solve the recurrence using the Master Theorem: $T(n) = 5T\left(\frac{n}{4}\right) + n\lg \lg n$

I am trying to solve the recurrence: $$ T(n) = 5T\left(\frac{n}{4}\right) + n\lg \lg n. $$ I tried to apply the Master Theorem but it didn't get me anywhere: $$ a=5,\; b=4\; \text{ and } f(n) = n\lg ...
0
votes
1answer
14 views

find the asymptotic upper bound

I need to find the asymptotic upper bounds in $O$ notation for $T(N)$ in two recurrences. Assuming that $T(N)$ is constant for sufficiently small $N$, I need to make the bounds as tight as possible. ...
3
votes
0answers
15 views

Weak convergence and convergence of moments

Consider a random variable $X$ defined on the probability space $(\Omega, \mathcal{F}, P)$ such that $X:\Omega\rightarrow \mathbb{R}$. Suppose that $X\sim N(\mu, \sigma^2)$. Consider a random ...
1
vote
2answers
61 views

Show that $1^k+2^k+\cdots+n^k$ is $\Omega (n^{k+1})$

...where k is a positive integer. The Big Oh case is not so hard. But how do I show that $1^k+2^k+\cdots+n^k$ is $\Omega (n^{k+1})$?
0
votes
2answers
29 views

Prove or Disprove Θ

I want to prove or disprove that $3n^3 +n^2\log(n) = Θ(n^3)$. I'm aware that I will need to either prove or disprove both big-o and big-Ω to prove or disprove Θ. I am simply struggling to do so. Help ...
2
votes
2answers
35 views

Proof based on definition of big-$O$

I want to prove that $n! = O(n^n)$ based on the definition of big-$O$. I find it pretty easy to show that $n! = O(n^n)$ by simply showing that $n (n-1) < n \cdot n \ldots$ etc. However I can't ...
0
votes
1answer
29 views

Prove that $\sum_{i=0}^{k} \lg \frac{n}{2^i} = \Theta(\lg^2 n)$

Show that if $n$ is a power of $2$, say $n = 2^k$, then we have the equality $\sum_{i=0}^{k} \lg \frac{n}{2^i} = \Theta(\lg^2 n)$. The first step is to prove $O(\lg^2n)$: $$ \lg \frac{2^k}{2^0} + \lg ...
0
votes
0answers
16 views

Can you analyze this identity involving the sum of divisors function and $rad(n)=\prod_{p\mid n}p$?

Let $\sigma(n)$ the sum of divisors function, then by Mobius inversion formula $$\sigma(n)=n-\sum_{\substack{d\mid n,d<n}}\sigma(d)\mu\left(\frac{n}{d}\right),$$ and since this function is ...
1
vote
1answer
18 views

$a_n\geq b_n$ for $n>\bar{n}$ implies $\limsup_{n\rightarrow \infty}a_n\geq \limsup_{n\rightarrow \infty}b_n$

Consider two sequences of real numbers $\{a_n\}_n, \{b_n\}_n$. I know that if $a_n\geq b_n$ $\forall n$ then $\limsup_{n\rightarrow \infty}a_n\geq \limsup_{n\rightarrow \infty}b_n$. Suppose ...
-1
votes
0answers
23 views

Is $ \lfloor {\log(n)} \rfloor!$ or $ \lfloor {\log(\log(n))} \rfloor!$ polynomially bounded? [closed]

Which of these is is polynomially bounded: $ \lfloor {\log(n)} \rfloor!$ $ \lfloor {\log(\log(n))} \rfloor!$ I think both are but I can't prove it.
2
votes
2answers
42 views

Can you get a closed-form for $\sum_{j=0}^{\infty}\frac{2^{2j-1}B_{2j}}{(2j)!}$?

Let $B_{k}$ the kth Bernoulli number, then using their asymptotic I can justify the absolute convergence of this series $$\sum_{j=0}^{\infty}\frac{2^{2j-1}B_{2j}}{(2j)!},$$ since, if there are no ...
1
vote
0answers
42 views

Big-Theta - asymptotic bound - is solution sufficient enough?

I am wondering is my solution sufficient enough (or detailed enough) for the following question? or it is even a valid solution? Question: Find a tight asymptotic bound ($\Theta$) in terms of the ...
0
votes
1answer
29 views

Bounded away sequence implications

Consider the sequence $\{\sqrt{n}|a_n-a|\}_n$ where $a_n, a \in \mathbb{R}$. Assume $\{\sqrt{n}|a_n-a|\}_n$ is bounded away from $0$ and $\infty$. Is this equivalent to or sufficient or necessary for ...
-1
votes
0answers
16 views

$f(a)\leq g(a)\in (o(a))^{\frac{1}{2}}$ implies $f(a)\in o(a)$

Consider the real-valued functions $f,g$ such that $f(a)\leq g(a)\in (o(a))^{\frac{1}{2}}$ as $a \rightarrow 0$, where $o(\cdot)$ denotes little o notation explained here. In order to show $f(a)\in ...
1
vote
1answer
18 views

Implications of $n a_n=O((n^{\frac{1}{\alpha}}|b_n|)^\alpha)$

Consider two sequences of real numbers $\{a_n\}_n$, $\{b_n\}_n$. Suppose $n a_n=O((n^{\frac{1}{\alpha}}|b_n|)^\alpha)$ where $\alpha \in \mathbb{R}$, $na_n\geq 0$ and big $O$ notation is explained ...
4
votes
2answers
39 views

Sequence bounded away from $0$ and $2$

Suppose I have a sequence of real numbers $\{a_n\}_n$ and I'm told that $\{a_n\}_n$ is bounded away from $0$ and $2$. (1) What does it mean exactly? My thinking is that it means $a_n\neq 0$ and $a_n ...
1
vote
0answers
31 views

What is the probaility that two random permutations have same order?

I am interested in the orders of random permutations. Since the law of the log of the order of a permutation converges to a normal law (for instance Erdös-Turan Statistical group theory III), one ...
1
vote
2answers
38 views

Is it true that $ f(n) = O(g(n))$ implies $g(n) = O(f(n))$

So I have this is an assignment for algorithms. I've googled a lot, read the chapter in the book about big Oh notation, and I understand the concept. I do not however understand how to prove it. I ...
0
votes
0answers
25 views

Solve the Recurrence Relation to Get a Theta Bound

If I have $T(n)=T(n-5)+n$, how would I go about using induction to find a $\Theta$ bound for this. I was able to use a tree method to get that the bounds should be about $\frac{n^2}{5}$, but I am ...
1
vote
2answers
36 views

Analyze for loop with if statement

I have this rather complicated loop: sum=0 for i=1 to n do for j=1 to i^2 do if(j (mod i) = 0) then for k=1 to j do sum++ ...
0
votes
0answers
37 views

Algorithm For Honest vs. Dishonest People

Consider a group of people. When two are taken and asked if the other is honest, they may each either reply that the other is honest, dishonest, or they may report that one is honest and the other is ...
0
votes
0answers
35 views

Show that $\lim_{n\rightarrow \infty} (1-\omega(\frac{1}{n}))^n=0$ and $\lim_{n\rightarrow \infty} (1-o(\frac{1}{n}))^n=1$

Could you help me to show that (1) $\lim_{n\rightarrow \infty} (1-\omega(\frac{1}{n}))^n=0$ (2) $\lim_{n\rightarrow \infty} (1-o(\frac{1}{n}))^n=1$ where $o(\cdot)$ is little $o$ notation described ...
1
vote
2answers
31 views

Order of growth of logarithms, compared to linear

I think it is true that any power of a logarithm, no matter how big, will eventually grow slower than a linear function with positive slope. Is it true that for any exponent $m>0$ (no matter how ...
0
votes
0answers
13 views

Asymptotic power of a test

Do you have any insight on the following statement Consider a test with a test statistic weakly convergent to a continuous distribution under any alternative and such that the finite sample power at ...
2
votes
1answer
36 views

Inquiry on big $O$ notation

As a deeply enthusiastic prospective undergraduate student, there are is a fact that i'm still to completely understand about the big $O$ notation, namely: Let $f(x), g(x) \neq x$ be nonconstant ...
0
votes
0answers
28 views

Find the simplest $g(n)$ such that $f(n) \in \Theta(g(n))$

Let $f(n) = \sum_{i=1}^n i^{-1}$. Would the simplest $g(n)$ be $1$? If we let $g(n) = 1$, then for all $n > 1$, $g(n) \le f(n)$. To construct an upper bound, observe that since $n$ is finite, ...
0
votes
2answers
16 views

asymptotic and monotonically increasing properties of prime factorization function?

Questions We define $A(x)= \text{number of prime factors of x}$ For example $A(2 \times 3^2) = 3$ I noticed when $s_k = \frac{N!}{\prod_j n_j}$ and $\sum_{j} n_j = N$ $$ s_1 < s_2 \implies ...
3
votes
1answer
41 views

Modified Laplace's method

In the application of Laplace method (or steepest descent) it is often assumed that the dependence on the factor N, on which we are expanding the integral, is only in the argument of the exponential. ...
0
votes
1answer
20 views

Find a function $f(n)$ such that neither $f(n) = O(log n)$ nor $f(n) = \Omega(n)$ holds.

Any hints on this problem? I want to find a function $f(n)$ which is: NOT $f(n) = O(log n)$ NOT $f(n) = \Omega(n)$ So it must hold that: $c_1 * log n < f(n) < c_2 * n$ and $c_1, c_2$ are ...
2
votes
1answer
92 views

Asymptotics of “ugly” function elucidate Goldbach's conjecture?

Question We now define the following "ugly" function: $$ A_c(s,r,n,m) = \begin{cases} 1 & \text{ if only $sr+nm=2c$ } \\ 0 & \text{otherwise} \end{cases} $$ How does the ...
0
votes
1answer
18 views

Asymptotic bounds on sum of primes

Let $p_i$ denote the $i$th prime number, and let $p_k\#$ denote the $k$th primorial, $p_k\# \overset{\textrm{def}}= \prod_{i \le k} p_i$. I am interested in asymptotic upper bounds for the ...
3
votes
0answers
33 views

Distinct prime factorization function formulation to find mobius function?

Background I recently noticed the following: $$ S(x)=\sum_{r=1}^\infty x^{p_r} $$ where $p_r$ is the $r$'th prime: $$ \sum_{r=1}^\infty S(x^r) = \sum_{r=1}^\infty \frac{x^{p_r}}{(1-x^{p_r})} $$ ...
0
votes
0answers
3 views

Asymptotic runtime of $f(n)$ in the Master Method

The Master Method helps us solve recurrences of the form: $$T(n)=aT(\frac{n}{b})+f(n).$$ If $f(n)$ is convoluted, is there any point in examining the terms beyond the highest order ones? Suppose for ...
0
votes
0answers
23 views

Master Theorem for common recurrence

I have the following recurrence: $$T(n) = T\bigg(\frac{n}{2}\bigg) + O(n)$$ And I am trying to find the time complexity using the master theorem. So I have: $a = 1, b = 2$ $f(n) = O(n) = c(n)$ ...
1
vote
0answers
16 views

Estimating the sum $\sum_{y \in \Bbb{Z}^d} (|y|+1)^{-\alpha}(|x-y|+1)^{-\beta}$ as $|x| \to \infty$

I would like to know a rather precise asymptotics of the sum $$ S(x) = S_{\alpha,\beta}(x) := \sum_{y \in \Bbb{Z}^d} \frac{1}{(|y| + 1)^{\alpha}(|x-y| + 1)^{\beta}}$$ as $|x| \to \infty$. Here, ...
0
votes
2answers
57 views

Big-Oh Analysis of For Loop

I have the following for loop: sum = 0 for i = 1 to n do for j = 1 to i^3 do for k = 1 to j do sum++ What is the strategy to determine ...