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
1answer
13 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
29 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
15 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 ...
0
votes
1answer
1k views

What is the computational complexity of a brute force perfect numbers finder algorithm?

A loop goes thru all numbers from one to N to find perfect numbers. For each number in the range, it checks all numbers less than it to see if it's a divisor by modding it by the number and checking ...
0
votes
0answers
15 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 ...
2
votes
2answers
22 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
1answer
25 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 ...
0
votes
0answers
26 views

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

What is the asymptotic growth rate of $\frac1{\zeta(n)}$? Is it polynomial in $n$?
2
votes
1answer
51 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 ...
0
votes
2answers
45 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 ...
-1
votes
1answer
23 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
28 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
29 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
15 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. ...
2
votes
2answers
39 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
2answers
32 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 ...
1
vote
2answers
71 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
1answer
40 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
20 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
33 views

Showing that $\log{\log^d{3n}} = O(\log{\log^d{n}})$

I'm trying to show this: $$\log{\log^d{3n}} \leq q\cdot \log{\log^d{n}} \;\;\exists\, q,k > 0,\forall n>k, \text{where } d \text{ is a constant} > 0$$ This is what I have so far ...
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 ...
2
votes
2answers
44 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
49 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
30 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
vote
1answer
22 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 ...
1
vote
2answers
37 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++ ...
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
35 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
50 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 ...
1
vote
2answers
38 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
36 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 ...
0
votes
0answers
14 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
41 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
30 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
17 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 ...
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
50 views

Accelerated Order of Convergence

Let $m > 0$ and $ a:[0,1] \rightarrow \mathbb R$ be a function with $a(\epsilon) \rightarrow 0$. Then $ \epsilon^m a(\epsilon) \rightarrow 0 $ for $ \epsilon \rightarrow 0$. But is $ \epsilon^m ...
3
votes
1answer
48 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
35 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 ...
0
votes
1answer
26 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 ...
4
votes
2answers
192 views

Euler-Maclaurin Summation

Using EM summation formula estimate $$ \sum_{k=1}^n \sqrt k $$ up to the term involving $\frac{1}{\sqrt n}$ My attempt is $$ \sum_{k=1}^n \sqrt k = \frac{2 \sqrt{n^3}}{3} -\frac{2}{3} + \frac 1 ...
3
votes
0answers
36 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
6 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
2answers
72 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 ...
0
votes
0answers
27 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
22 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, ...
2
votes
1answer
89 views

Swapping the order of limits in combinatoric?

Part $A$ Let a power series be $ \sum_{r=1}^\infty x^{a_r}$ Now, we are interested square of the power series with the condition: $$ \sum_{m=1}^\infty \sum_{n=1}^\infty x^{a_m + a_n} = ...
0
votes
0answers
27 views

The minimum of two big-O functions

Suppose we have the following lower and upper bounds for an invariant $\chi(G_N)$, where $G_N$ is a graph on $N$ vertices, $N=f(k,n,m) $ and $N,k,n,m\in \mathbb{N}$: $$ ...
1
vote
0answers
7 views

Calculation of Running time of array when size increase by constant

I am learning data structure and running time calculation. I got a problem to understand the running time calculation of increasing the size of the array. 1) if we increase the size of the array by ...
0
votes
0answers
24 views

Big-Oh, Big-Omega, Big-Theta determination

I am given a recurrence relation and told to solve it. Once we solve it we are supposed to determine whether it is in $O(f(n)), \Omega(f(n))$, or $\Theta(f(n))$. The relation is $t_n = 2nt_{n-1}$. ...