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

learn more… | top users | synonyms (1)

12
votes
1answer
121 views

Divergent function of ratio must be logarithm

Given. Consider two functions $F(t)$ and $r(t,x)$ such that $\lim_{t\to\infty} F(t) = \infty$ and $\lim_{t\to\infty} r(t,x)$ is finite for any $x$. ($x$ and $t$ are always positive in what follows.) ...
2
votes
0answers
97 views

Number-theoretic asymptotic looks false but is true?

Question Let $p_r$ be the $r'th$ prime. Is it true that, $$\sum_{r=1}^\infty s^r \ln(p_r) \sim \frac{s}{(1-s)} $$ I know this looks bizarre but kindly consider the argument below. I'm also ...
11
votes
2answers
370 views

Known bounds for the number of groups of a given order.

The number of nonisomorphic groups of order $n$ is usually called $\nu(n)$. I found a very good survey about the values. $\nu(n)$ is completely known absolutely up to $n=2047$, and for many other ...
0
votes
0answers
17 views

Showing $n^3 = \Omega ((n+7)^3)$

Prove/Disprove: $n^3 = \Omega ((n+7)^3)$ Pretty sure it's correct since both sides have the same degree, so if we replace all the degrees 1 and 2 expressions from the RHS with $n^3$, we get ...
27
votes
9answers
7k views

What is the purpose of Stirling's approximation to a factorial?

Stirling approximation to a factorial is $$ n! \sim \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n. $$ I wonder what benefit can be got from it? From computational perspective (I admit I don't ...
0
votes
2answers
40 views

How do I use L'Hopital's rule to determine if $\log^kN$ is $o(N)$ for any constant $k$?

How do I apply L'Hopital's rule to see if $\log^kN$ is $o(N)$ (small $o$) for any constant $k$? I understand I should keep finding the derivatives of both functions and stop if I can clearly identify ...
3
votes
0answers
97 views

Combining Firoozbakht's conjecture and abc conjecture

Firoozbakht's conjecture states that for all $n\geq 1$ $$p_n^{\frac{1}{n}}>p_{n+1}^{\frac{1}{n+1}},$$ where $p_k$ the kth prime number. By asumption of this conjecture, for a fixed $n$, there is a ...
0
votes
0answers
33 views

Recurrence relation to find run time-complexity

int function(int n){ if (n<=1) return 1; else return (2*function(n/2)); } What is the recurrence relation $T(n)$ for running time, and why ? I believe is ...
1
vote
2answers
59 views

Asymptotics of $\sum_{n\leq x}d(kn)$ where $k$ is composite

As shown by @NoamD.Elkies here, $\sum_{n \leq x} d(kn)$ can be reduced to a linear combination of values of $D$ at multiples of $x$ (where $D(x)=\sum_{n\leq x}d(n)$ is the sum of the number of ...
0
votes
2answers
19 views

Given the time complexity, determine how many problem instances can be solved in one minute

I have this question: Suppose you have a computer that requires 1 minute to solve problem instances of size $n = 7.3000\cdot 10^4$. What instance sizes can be run in 1 minute if you buy a new ...
1
vote
1answer
31 views

Why is this $O(\log \log n)$?

Why is this $O(\log \log n)$? // Here c is a constant greater than 1 for (int i = 2; i <=n; i = pow(i, c)) { // some O(1) expressions } I am ...
0
votes
1answer
19 views

Finding $\sum_{i=0}^{log_2n}(\log n -i)$

Find $\displaystyle\sum_{i=0}^{log_2n}(\log n -i)$ Just to make sure I got it using a change of variable: $\displaystyle\sum_{i=0}^{log_2n}(\log n -i)= \sum_{k=0}^{\log n}k =\Theta (\log ^2 n)$ ...
1
vote
0answers
30 views

Is my proof valid for $\log(n!) = \Theta(n \log n)$?

Is my proof valid for $\log(n!) = \Theta(n \log n)$? First I prove that $\log(n!) \leq cn \log n$ for some positive $c$ for all $n \geq n_0$. Since $n! \leq n^n$, it follows that $\log(n!) \leq ...
1
vote
1answer
38 views

Big O notation times zero

Consider a real-valued sequence $\{h_n\}_n$ such that $$(\star) \lim_{n\rightarrow \infty}h_n=0$$ In order to show that $0*O(h_n^2)=0$ do we need to use assumption $(\star)$? Why?
3
votes
2answers
59 views

Convergence of prime zeta function for $\mathfrak R(s)=1$?

By doing some estimates for the partial sums of the Prime zeta function $P(s)=\sum_p p^{-s}$ for $\mathfrak R(s)=1$ I got that $P(1+i\alpha)$ converges for every $\alpha\neq0$... Since I did not ...
0
votes
1answer
28 views

Simplifying expressions with Big O notation

Consider a real-valued sequence $\{h_n\}_n$ with $\lim_{n \rightarrow \infty}h_n=0$. Could you help me to simplify $(O(h_n^2))^2+3O(h_n^2)$? My attempt: (1) ...
1
vote
1answer
27 views

How to prove $3h_n^2+o(h_n^2)\in O(h_n^2)$

Could you help to go through this operations with little-o and big-O notation? Consider the real-valued sequences $\{A_n\}_n$ and $\{h_n\}_n$ and suppose $\lim_{n \rightarrow \infty} h_n=0$. Let $$ ...
4
votes
0answers
65 views

Dealing with a difficult sum of binomial coefficients, $\sum_{l=0}^{n}\binom{n}{l}^{2}\sum_{j=0}^{2l-n}\binom{l}{j} $

I am interested in finding an upper bound for the sum $$F(n)= \sum_{l=0}^{n}\binom{n}{l}^{2}\sum_{j=0}^{2l-n}\binom{l}{j}.$$ Ideally it should be possible to evaluate it exactly using some ...
1
vote
0answers
14 views

Relation between stochastic and deterministic big O

Could you help me to clarify the relation between stochastic and non-stochastic Big O notation? Suppose I have a sequence of real-valued random variables $\{X_n\}_n$ defined on the probability space ...
1
vote
0answers
10 views

Inequalities with stochastic Big O

I have a very general question related to inequalities containing stochastic big o notation. Introduction: consider two sequences of real-valued random variables $\{X_n\}_n$, $\{Y_n\}_n$ ...
1
vote
1answer
25 views

Implications of convergence in probability

Consider two sequences of real-valued random variables $\{X_n\}_n$, $\{Z_n\}_n$ defined on the probability space $(\Omega, \mathcal{F}, \mathbb{P})$. Suppose that (1) $Z_n\in o_p(1)$, i.e. $Z_n$ ...
1
vote
0answers
19 views

Properties of stochastic little o notation

I have a question related to stochastic little o properties. Let $\{X_n\}_n$ be a sequence of real-valued random variables defined on the probability space $(\Omega, \mathcal{F}, \mathbb{P})$ such ...
0
votes
0answers
13 views

Showing that $f(x) \leq O(g(x))$.

I have two (strictly) positive functions $f(x)$ and $g(x)$ defined on $\mathbb{R}$. I am required to show that $f(x) \leq O(g(x))$ for $x \to \pm \infty$. I showed that $f(x) \leq kg(x)$ for $|x| \to ...
2
votes
1answer
48 views

Solving $T(n)= T(\frac n 2) + 2 T(\frac n 4) + n$

Solve $T(n)= T(\frac n 2) + 2 T(\frac n 4) + n, T(1)=1$ Each vertex in the tree has 3 children, we have up to the $\log _4 n $ level a complete tree, that has $3 ^{\log_4 n}$ vertices on that ...
1
vote
3answers
58 views

Solving $\sum_{i=0} ^{\log n} i2^i$

Solve (or simplify): $$\sum_{i=0} ^{\log n} i2^i$$ (without integrals) Trying to change the parameter: $j=i2^i$, so since $ 0\le i \le \log n$, then the maximum value for $j$ is when $j=n\log n$. ...
0
votes
0answers
25 views

finding theta notation with limit rule

I'm stuck at this problem while i using limit rule $$f(n) = 4\sqrt x $$ $$g(n) = (\log x)^2$$ $$\lim_{ n \to \infty} {4\sqrt x \over 5{(\log x)^2}}$$ i know that $f(n) = 4\sqrt x $ is asymtoticly ...
0
votes
1answer
25 views

Find asymtotic notation with limit rule

I'm stuck at this problem while i using limit rule $$f(n) = 3^{n\over 2}$$ $$g(n) = 2^{n\over 3}$$ $$\lim_{ n \to \infty} {3^{n\over2} \over 2^{n\over3}}$$ i think that the answer is $f(n) = ...
0
votes
1answer
55 views

Finding an upper bound of $ T(n) = \sqrt{n} T \left(\sqrt n \right) + n$

$$T(n) = \sqrt{n} T \left(\sqrt n \right) + n, n>1$$ $$T(n) = k, n\le1$$ My book says for upper bound to simplify to $$T(n) \le \sqrt{n}c\sqrt n\log\left(\sqrt n\right) + n$$ $$ = ...
4
votes
1answer
716 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 ...
4
votes
1answer
162 views

If an entire function satisfies $|f(z)| \leq C e^{M|z|}$, then $f(x)$ can't decay super-exponentially as $x\to\infty$

Let $f$ be a non-zero entire function. Suppose there are positive real numbers $C$ and $M$ such that $|f| \leq C e^{M|z|}$. Show that there is no function $g(x)$, defined on $x>0$ with ...
5
votes
3answers
248 views

How can I find $\lim_{n\to\infty}\int_0^\infty\frac{n\cos^2(x/n)}{n+x^4}dx$?

I am trying to find the value of this integral: $\displaystyle{\lim_{n\to\infty}\int_0^\infty\frac{n\cos^2(x/n)}{n+x^4}dx}$. The integrand tends to 1 as $n$ goes to infinity. So if some convergence ...
1
vote
1answer
28 views

Error in the CLRS book for analyzing time complexity?

4.3-8 Using the master method in Section 4.5, you can show that the solution to the recurrence $T(n) = 4T(n/2) + n^2$ is $\Theta(n^2)$. Wouldn't it be $\Theta(n^2 \log n)$?
2
votes
0answers
40 views

Asymptotic Calculus [closed]

Assuming I have an equation of the form $$f(x) = g(x)$$ How can I solve it via asymptotic expansion? For example: $$2 + 2x + 4x^2 = e^{2x}$$
0
votes
0answers
11 views

Showing $\frac n {log_2 n} = \Omega (n^{\frac 1 {100}})$ and another

Prove: $\frac n {log_2 n} = \Omega (n^{\frac 1 {100}})$ $3^{log_a {n}} = O(3^{log_b {n}})$ where $a>b>0$ For 1 we need to show that: $\frac n {log_2 n} \ge c (n^{\frac 1 ...
1
vote
2answers
42 views

How to show that for all k, $k! \ge (k/2)^{k/2}$

I'm working on a homework problem that has me showing a "$\Omega(n\log k)$ lower bound on the number of comparisons needed to sort a sequence of $n$ elements, when the input sequence consists of ...
2
votes
4answers
38 views

O(n) of given code

sum = 0 for (i = 0; i < n; i++) for (j = 0; j < i * i; j++) for(k = 0; k < n; k++) ++sum Here is my work The outer most loop: ...
1
vote
1answer
26 views

Meaning of “polynomially larger”

For example Is $n$ polynomially larger than $\frac{n}{\log n}$? Than $n \log n$? Is $n^2$ polynomially larger than $\frac{n}{\log n}$? Than $n \log n$? I am trying to understand the difference ...
0
votes
0answers
33 views

Summation approach for $T(n) = 3T\left(\frac n3\right) + \sqrt n$

Finding an approximation for $T(n) = 3T\left(\frac n3\right) + \sqrt n$ I tried to solve this: Proving that $T(n) = 3T\left(\frac n3\right) + \sqrt n = \Theta(n)$ in a different approach but I'm ...
0
votes
0answers
24 views

A question about a sequence of sets of prime numbers deduced from Euclid strategy

Let the sequence of sets of prime numbers defined by $$S_1=\{2\},$$ and for $n>1$ $$S_n=S_{n-1}\bigcup\{\text{p prime such that p divides } 1+\prod_{s_i\in S_{n-1}}s_i\}.$$ Examples. We have ...
2
votes
0answers
89 views

Boundary layer method

I am trying to solve the following differential equation using boundary layer method. $$\psi ''(z) + \frac{1}{z} \psi'(z)\left(3 - \displaystyle\frac{4}{1+(\frac{z}{zc})^8}\right)+ ...
0
votes
0answers
11 views

Sufficient conditions for $|\hat{\theta_n}-\theta_0|=O_p(1/\sqrt{n})$

Let $X_1,\ldots,X_n$ be i.i.d. random variables defined on a probability space $(\Omega, \mathscr{F}, P)$ admitting some true unknown density $f_{\theta_0}$, with $\theta_0$ belonging to $\Theta ...
0
votes
1answer
40 views

Asymptotic expansion question

How may I use Watson's Lemma to find the full asymptotic expansion for; $$ I(\lambda)= \int_0^\infty e^{-\lambda(1+s)}ln(1+s^2)ds $$ as $\lambda \rightarrow \infty$. Thanks in advance
-1
votes
0answers
30 views

Calculating run times of loops with theta notation using summation

When calculating the run time of programs using asymptotic notation, I know how to set up the sums for things like for loops, but I'm getting stuck on summing them up. ...
2
votes
0answers
56 views

Integral of a Gaussian with Trigonometric functions Involved

I am having a difficult time evaluating an integral unlike any integral I have seen before. To get right into things here is the integral: $$\frac{A}{\sigma_o\sqrt{2\pi}}\int_{-\infty}^\infty ...
1
vote
1answer
16 views

Asymptotic elements of a sequence of of gaps given the average asymptotic function.

If the average consecutive difference of a sequence of numbers is asymptotically the same as $f(n)$. Then what can be said about numbers in the sequence, asymptotically as $n \to \infty$. Let ...
2
votes
1answer
50 views

Nested radicals with logarithms

The Wikipedia page about Nested radicals lists the following formula: $$ \sqrt{n+\sqrt{n+\sqrt{n+\sqrt{n+\cdots}}}} = \tfrac12\left(1 + \sqrt {1+4n}\right) = \Theta(\sqrt{n})$$ Suppose we replace ...
0
votes
2answers
33 views

What is the value of C in $O(x^n)$ definition?

I read the definition that $f$ is in $O(x^n)$ if $|f(x)|<C|x^n|$ for some $C$. I'm struggling to understand how to check this. For example, supposedly $f(x) = 5x+3x^2$ is in $O(x)$ but not ...
1
vote
1answer
25 views

Asymptotic bound with square-roots

Let $f(n)$ and $g(n)$ be two increasing functions of $n$ such that: $$ f \leq g + O(\sqrt{g}) + O(\sqrt{f}) $$ Is it true that: $$ f \leq g + O(\sqrt{g}) $$ ? If not, then what would be a good ...
1
vote
1answer
80 views

Can this integral be evaluated/approximated?

I've been trying to evaluate this integral without much success: $\displaystyle \int_{-\infty}^\infty dx\, e^{iax} \frac{1- e^{-c\sinh^2 bx}}{\sinh^2 bx}$ I've tried contour integration. There are no ...
3
votes
1answer
71 views

Asymptotic expansion of $f(x)= \sum_{n=1}^\infty \frac{\sin nx}{\sqrt{n}}$ at the origin

The function $$f(x)= \sum_{n=1}^\infty \frac{\sin nx}{\sqrt{n}}$$ is odd, uniformly convergent on all intervals $[\epsilon,\pi]$ for $0 < \epsilon < \pi$. Hence $f$ is continuous on $(0,\pi]$. ...