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

Finding asymptotic relationship between: $\frac {\log n}{\log\log n} = (?) (\log (n-\log n))$

Given $f(n)=\frac {\log n}{\log\log n} , g(n)= (\log (n-\log n))$, what is the relationship between them $f(n)=K (g(n))$ where "K" could be $\Omega,\Theta,O$ I thought of taking a log to both ...
0
votes
0answers
20 views

Solve recurrence equation $T(n) = 9T\left(\frac{n}{18}\right) + 3T\left(\frac{n}{9}\right) + T\left(\frac{n}{3}\right) + n^\frac{3}{2}$

I need to solve the following equation $$T(n) = 9T\left(\frac{n}{18}\right) + 3T\left(\frac{n}{9}\right) + T\left(\frac{n}{3}\right) + n^\frac{3}{2}$$ The depth of the recursion tree is $log_3n$. I ...
2
votes
1answer
38 views

A strange identity related to the imaginary part of the Lambert-W function

Working on a problem in QFT, i was stumbeling about some expressions containing the Lambert-$W$ function. Playing around, i discovered experimentally that the following statement seems to be true ...
-1
votes
0answers
15 views

Give the simplest possible Theta ($\Theta(· · ·)$) form for each of the following functions (e.g., $2n + 3$ would be written as $\Theta(n)$?) [on hold]

1) $2n^2 + 5n + 3$ simplified to $(2n+3)(n+1)$ $\Theta(n)(n+1)$. What would $(n+1)$ be? 2) $5n + 3 \log n + 7$ 3) $2n + 3n \log n + 3$
1
vote
0answers
37 views

Can you estimate the difference of primes between numerator and denominator?

Let $p_n$ the nth twin prime, it is $p_n$ is a prime number and $2+p_n$ is also a prime. It is well know that Brun's theorem states (unconditionally) that $$\mathcal{B}=\sum_{n\geq ...
8
votes
0answers
46 views

Eigenvalue problem for $−\psi''(x) − (ix)^ N \psi(x) = E\psi(x)$ in complex plane

To find the eigenvalue $E$ in the complex plane of $x$ for one dimensional Schrodinger equation $$ −\psi''(x) − (ix)^ N \psi(x) = E\psi(x). $$ where $N$ can be any real number, the boundary condition ...
1
vote
2answers
19 views

Big-oh and Small-oh Notation: Ratio.

Is it possible to say something about the order of ratios like $O(1/n^2)/o(1)$ or $O(1/n^2)/O(1/\sqrt{n})$?
0
votes
1answer
23 views

does $f(n) = O(g(n))$ implies $(f(n))^{log(n)} = O((g(n))^{log(n)}) ?$

if $f(n)$ and $ g(n)$ are monotonically increasing, and $f(n) = O(g(n))$. Does it imply that $(f(n))^{log(n)} = O((g(n))^{log(n)}) ?$ Well I had a go at it saying I need to show that ...
2
votes
4answers
40 views

Showing that Harmonic numbers are $\Theta(\log n)$, intuitively

I wish to verify that Harmonic numbers $H_n = \sum_{k=1}^{n} \frac{1}{k}$ are $\Theta(\log n)$. One idea I have is to approximate the sum with an integral: $$\int_{1}^{n} \frac{1}{k} ~dk = \log(n) - ...
1
vote
2answers
46 views

Big O notation: ratio of two $O(\cdot)$'s is $O(\cdot)$ of the ratio?

Is it true that if $f_1=O(g_1)$ and $f_2=O(g_2)$ then $$\frac{f_1}{f_2}=\frac{O(g_{1})}{O(g_{2})}=O\!\left(\frac{g_1}{g_2}\right)$$ ?
2
votes
0answers
39 views

Asymptotic behaviour of an integral depending on a parameter

I am trying to compute the asymptotics on $t$ of the following integral: \begin{equation} I(t)=\int_{\mathbb{R}^{n}}e^{-|\lambda|^{2}/2t}\prod_{i<j}\left( e^{\lambda_{j}/t}-e^{\lambda_{i}/t} ...
4
votes
1answer
27 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
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
26 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
11 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
31 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
10 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 ...
4
votes
0answers
37 views
+250

Finding where the tail starts for a probability distribution, from its generating function

Suppose we generate "random strings" over an $m$-letter alphabet, and look for the first occurrence of $k$ consecutive identical digits. I was with some effort able to find that the random variable ...
0
votes
1answer
22 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
17 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
25 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
19 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
31 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
36 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
33 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
20 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
40 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
26 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
32 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
38 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 ...