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
1answer
32 views

Big O notation proof for a divided problem

I have a problem: the algorithm is dividing the given problem into two subproblems - one is 3/5 big and another is 4/5 of the size of the problem - and then merges those two parts together in a linear ...
1
vote
2answers
51 views

How can I show that $\sum \limits_{i=1}^n i^2$ is $O (n^3)$

I am preparing for an exam, and one of the problems on the study guide is: Show that $\sum \limits_{i=1}^n i^2$ is $O (n^3)$ If we declare n as some arbitrary number 5, then our summation would ...
20
votes
6answers
1k views

Is there a slowest rate of divergence of a series?

$$f(n)=\sum_{i=1}^n\frac{1}{i}$$ diverges slower than $$g(n)=\sum_{i=1}^n\frac{1}{\sqrt{i}}$$ , by which I mean $\lim_{n\rightarrow \infty}(g(n)-f(n))=\infty$. Similarly, $\ln(n)$ diverges as fast as ...
1
vote
1answer
19 views

Order estimates

QUESTION: Suppose $y(x) = 3 + O (2x)$ and $g(x) = \cos(x) + O (x^3)$ for $x << 1$. Then, for $x << 1:$ (a) $y(x)g(x) = 3 + O (x^2)$ (b)$ y(x)g(x) = 3 + O (x^4)$ (c) $y(x)g(x) = 3 + O ...
2
votes
1answer
37 views

what is wrong with this proof? (proving the transitive property of Big O)

So the problem is if $f(n) \in O(g(n))$,and $g(n) \in O(h(n))$ then $f(n) \in O(h(n))$ Assume $f(n) \geq 0, g(n) \geq 0, h(n) \geq 0$ Proof: From assumptions, ...
2
votes
1answer
102 views

Bound the probability of unlikely escape through one end of a thin rectangle

Consider the following elliptic PDE boundary value problem, \begin{eqnarray} & a u_x + b u_y + \frac{\alpha}{2} u_{xx} + \beta u_{xy} + \frac{\gamma}{2} u_{yy} = 0 \;, \quad {\rm ~for~} ...
3
votes
1answer
41 views

Big O Notation and negative “n”

So I'm studying big $O$ notation right now and am working through a problem and got $O(x^{-10})$ and I'm just wondering if it's possible to even have a term with $O(x^{-n})$ because I've never come ...
2
votes
2answers
44 views

Use Laplace's method with $\int_{0}^{\infty} e^{x(3u-u^3)}du$ as $x\rightarrow \infty$

Use Laplace's method with $\int_{0}^{\infty} e^{x(3u-u^3)}du$ as $x\rightarrow \infty$. I'm confused about how to taylor expand about u=1? How do I continue? Obviously first of all I have converted it ...
1
vote
2answers
27 views

does $f(n) \neq O(g(n))$ implies $g(n)=O(f(n))$ [duplicate]

Im pretty sure it doesn't, but how can I be sure? Was thinking by using $$f(x) = \sin(x) + 2$$ and $$g(x) = \cos(x) + 2$$ Thanks!`
0
votes
1answer
26 views

Big Theta of this modification of the secondary branch of the Lambert W function

I am looking to find the big-$\Theta$ of $-W_{-1}(-\frac{a}{n})$ in terms of elementary functions where $a$ is a constant. Looking around and I find that this should be $O(\log(n))$ and with maxima I ...
3
votes
1answer
47 views

Show that $\int_{0}^{\infty} e^{ix(\frac{t^3}{3}+t)}dt \sim \frac{i}{x}$

Show that $\int_{0}^{\infty} e^{ix(\frac{t^3}{3}+t)}dt \sim \frac{i}{x}$ I thought that you would use the method of stationary phase, but the maximum of $\frac{t^3}{3}+t$ occurs at $+/- i$. So how do ...
0
votes
0answers
31 views

Finding the asymptotic expansion of $\sin(3x)$ using asymptotic sequence $\{\ln(1+x^n)\}_n$

Finding the asymptotic expansion of $\sin(3x)$ using asymptotic sequence $\{\ln(1+x^n)\}_n$. In the notes and lectures the only example that was given was an expansion for $\tan(x)$ where she ...
4
votes
3answers
85 views

How is $O(\log(\log(n)))$ also $O( \log n)$?

How is $O(\log(\log(n)))$ also $O( \log n)$? I have seen this result somewhere with this but I still didn't quite understand how this is true. This would also help me compute Big Omega of the ...
0
votes
0answers
204 views

CDF of sum of $3$ independent discrete uniform random variables on $\{1,2,\dots,n\}$

What is an approximate closed formula for this probability, with a derivation: $p(k,n)$ is the probability, that among $n$ PC disks and $k$ errors in sum on them, there will be at least $1$ disk ...
1
vote
0answers
44 views

Question about your function,

I'm Xavier Vigan, a physical oceanographer. I've been using your $f(x)=\dfrac 12 \times \left(X+C-\sqrt{S+(X-C)^2}\right)$ function to calibrate quantile vs quantile plots. Because of the shape of ...
0
votes
3answers
26 views

relationship between Big $O$ notation and limit

If I have a function $f(n)$ such that $f(n) \geq 0$ for all positive integers $n$ and that $\lim\limits_{n\to \infty} f(n) = 0$, then can I conclude that $f(n) = O\left( \dfrac{1}{n^k}\right)$ for ...
0
votes
4answers
55 views

Big-O notation — is it mainly used to classify rate of growth or rate of decay to zero?

For example, $e^{x} = 1 + x + x^2/2 + O(x^3)$, and we interpret $O(x^3)$ as the remainder term that goes to zero like $x^3$. What's the primary usage of Big-O notation? (strictly in math classes, ...
1
vote
0answers
37 views

What does $\mathbb P(\overline{\mathbf X} = \mathbf x)$ mean

I am reading Peter Hall's "the bootstrap and edgeworth expansion". In Theorem 2.3 on page 57, it claims that if the characteristic function $\chi$ of a $d$-dimension random variable $\mathbf X$ ...
3
votes
1answer
54 views

length of the curve $y=x^n$ in the unit square

Let $l_n$ be the length of the curve $y=x^n$ in $[0,1]\times[0,1]$. Then obviously $\lim_{n\to\infty}l_n = 2$. What about $\lim_{n\to\infty}(n(2-l_n))$ ? The formula $l_n = ...
0
votes
1answer
39 views

can use diagonal matrix in a formula to figure out how many characters would occur in all substrings of a string 's'?

Math experts - I'm working through a simple "big O" analysis of algorithms problem comparing two approaches to the longest substring problem. One approach is brute force: checking all possible ...
3
votes
1answer
47 views

Density of linear combination

Let $r_1, \ldots, r_n$ be a set of positive reals. Define \begin{equation*} S = \{a_1r_1+\cdots+a_nr_n : a_i\in \mathbb{N}\}. \end{equation*} Define $\pi(x)= |\{a\in S:a<x\}|$. Is there an ...
0
votes
1answer
24 views

Little o notation within another little o

To prove $e^{x + o (x)} = 1 + x$ as $x \rightarrow 0$, I can do it directly: $\lim_{x \rightarrow 0} \frac{\log (1 + x) - x}{x} \overset{\text{l'hopital}}{=}\lim_{x \rightarrow 0} \frac{(1 + x)^{- ...
0
votes
0answers
29 views

how to solve T(n)=T(Logn)+O(1)

Given That $T(1)=1$ Solve following recurrence function $T(n)=T(\log n)+O(1)$ I know the answer is $\log^* n$ but don't know how to prove it. What I tried: $\log(n)+\log(n-1)+\log(n-2)+...+1 = ...
2
votes
1answer
101 views

Growth of number of distinct elements

Let $A_k$ be a random variable which represents the number of distinct integers seen after sampling $k$ independently and uniformly at random from the range $1, \dots, n$. Let $B_k$ be a random ...
0
votes
3answers
1k views

merge sort vs insertion sort time complexity

How do I solve exercise 1.2-2 from Introduction to Algorithms 3rd Edition, Author: Thomas H. Cormen Would I need to set both sides equal to each other and solve for n?
2
votes
0answers
35 views

WKB leading order

I'm learning about the WKB method, and I'm applying it to an assignment. The assignment question asks to find the "leading order" WKB expansion for the particular equation. For WKB you make the ...
1
vote
2answers
67 views

Does $O(\log^2(x))$ imply $O(x)$

Does $O(\log^2(x))$ imply $O(x)$ I have to prove the following: $$\sum\limits_{\substack{n\in\mathbb N\\n\le x}}\Lambda(n)\log(n)=\psi(x)\log(x)+O(x)$$ Applying partial sum I get; ...
0
votes
0answers
11 views

Deriving information about asymptotics from finitness of a limit

Let $f_1,f_2:\mathbb{R}\setminus\{0\}\to \mathbb{R^+}$ be two $C^1$ functions and $\alpha:\mathbb{R}\setminus \{0\}\to \mathbb{R}$ be a function from a Zygmund class (in particular it is Holder for ...
1
vote
0answers
18 views

How to solve asymptotic recurrence without using Master Theorem

I am working on the following problem. Consider the function $B:\mathbb{N}\to\mathbb{R}$ defined by: $$B(n) = \begin{cases} 1 & \text{if $n\leq 2$,}\\ 3\cdot B(\lceil n/\log_2 n\rceil) + n & ...
4
votes
1answer
61 views

Product of two sets with density zero has density zero?

Let $A$ and $B$ be two subsets of $\mathbb N$ which have asymptotic density zero. Define $A\times B$ as the set of integers of the form $ab$ with $a\in A$ and $b\in B$. Must $A \times B$ also have ...
4
votes
1answer
38 views

Order of Growth of a Sum

Let $n>k$ and $r$ be arbitrary positive integers. Define $q=k/n$. I want to show that $$ \sum_{i=0}^{rk} \binom{rn}{i}q^i(1-q)^{rn-i}(rk-i)=\Theta(\sqrt{r}) $$ as $r\rightarrow \infty$. I've ...
0
votes
1answer
39 views

Why is $1 - \cos(x)$ of $\mathcal{O}(x^2)$?

I know the definition of order estimates, For the solution to apply we need to show: $ \displaystyle\lim_{x \to 0} \frac{1 - \cos(x)}{x^2} = A \neq 0\space or \space \infty$ But how can one show ...
2
votes
2answers
117 views

Approximation of binomial distribution with normal distribution

The Central Limit Theorem implies that near the center of mass we can approximate the binomial distribution with the normal distribution: $$ P(B(n,p) \geq i) \approx P(Z \geq \frac{i - n p}{\sqrt{n p ...
1
vote
2answers
17 views

Horizontal and Vertical Asymptotes of functions

So I'm completing a chart analyzing the different properties of three different functions: $f(x)=\log(x^2+6x+9), g(x)=\sqrt{x^2 -1}$ (sorry not sure how to do square roots on here), $h(x)=f(x)(g(x))$ ...
2
votes
1answer
46 views

Asymptotic of a complex integral

Consider the following integral $$f(x):=\int_x^{+\infty}re^{-(r+ir^2)}dr$$ I want to understand the asymptotic behavior of $f(x)$ as $x\rightarrow +\infty$ Thank you for any suggestion.
0
votes
1answer
92 views

Inverse of $x^x$ [duplicate]

Since $x^x$ grows very fast, its inverse should accordingly grow very slow, possibly slower than $\ln(\ln(x))$. I am troubled with finding such an inverse: I only get to the point: $\ln(x)x=\ln(y)$ ...
1
vote
1answer
58 views

Evaluate $\int_{x=0}^{\infty}\left(\frac{1}{\sqrt{x}}(1-e^{-x})\right)^{M-1}e^{-x}(1+sx)^{-N}dx,$

I am trying to evaluate $$\int_{x=0}^{\infty}\left(\frac{1}{\sqrt{x}}(1-e^{-x})\right)^{M-1}e^{-x}(1+sx)^{-N}dx,$$ where $s>0$, $M$ and $N$ are positive integers. But seem that the above integral ...
2
votes
2answers
27 views

Does one of these conditions on a sequence imply the other one?

Let ${(r_n)}_{n \geq 0}$ be a sequence of integers $\geq 2$. Set $q_n=\prod_{i=0}^{n-1} r_i$ (agreeing with $q_0=1$). I want to know whether one of these two conditions implies the other one (I think ...
1
vote
3answers
64 views

Upperbound confusion

Why is the following true? $3n^2-100n+6$ is big $O$ of $n^2$ This has been demonstrated to be true when $c$ is $4$ and $n$ is $10$. $3*100-1000+6 = -694 = 694$ is the absolute value is a big $O$ of ...
2
votes
2answers
48 views

Large $a$ asymptotics of $\int_0^{\pi/4} \exp(-a(x^2-\frac{x^4}{3}))$

I'm looking for a way to prove that $\displaystyle \int_0^{\pi/4} \exp(-a(x^2-\frac{x^4}{3}))dx=\int_0^{\pi/4} \exp(-ax^2)dx+o\left(\int_0^{\pi/4} \exp(-ax^2)dx\right)$ as $a$ goes to $\infty$ ...
1
vote
0answers
29 views

Proof $\log(cn)$ is in $\Theta(\log(n))$

How can I prove that $\log(cn)$ is in $\Theta(\log(n))$, where $c$ is a constant? I tried to prove $c_1\log(n) \le \log(cn) \le c_2\log(n)$, where $c_1$ and $c_2$ are also constants, but I'm having ...
1
vote
3answers
37 views

Show that $\lim_{n\to\infty}\frac{n}{(\log n)^2}=\infty$

I am working on an asymptotic analysis question from a data structures past paper, and I need to show that $$\lim\limits_{n\to\infty}\frac{n}{(\log n)^2}=\infty$$ Could I have a hint for working out ...
3
votes
3answers
77 views

Complete elliptic integral of the first kind $K(m)$ asymptotc expansion at $m = -\infty$

What is the asymptotic behavior of $K\left(-\frac{1}{\delta^2}\right), \delta > 0$ when $\delta$ tends to zero? Here $$ K(m) = \int\limits_0^{\pi/2} \frac{d\theta}{\sqrt{1 - m\sin^2 \theta}}, $$ ...
0
votes
0answers
19 views

Expected size of largest connected component in a binary matrix

Let $C_4(\mathbf M)$ and $C_8(\mathbf M)$ denote the size of binary matrix $\mathbf M$'s largest 4-connected component and 8-connected component of the same value, respectively. For example, the ...
3
votes
1answer
77 views

A proof involving an infinite sum

I am trying to prove that there exist constants $C_1 > 0$, $C_2>0$ such that$$C_1 \log N \geq\sum_{k=1}^\infty(1 - (1- 1/2^k)^N) \geq C_2\log N$$ where $N\in Z^+$. Could you please give me ...
0
votes
2answers
36 views

Show that $\sin(\mathcal{o}(x)) = \mathcal{o}(x)$ as $ x\to 0$

So I want to show that $\sin(\mathcal{o}(x)) = \mathcal{o}(x)$ as $ x\to 0$. So far I have thought that my result will come from showing $ \displaystyle \Big|{\frac{\sin(f(x))}{x}}\Big| \to 0$ as ...
8
votes
0answers
57 views

Decay of amplitude integral

Consider the function $$ f(\vec{x}) = \int_{\Bbb R^3} {\frac{ e^{-i\,\vec{x}\cdot\vec{k}}}{\sqrt{\vec{k}^2 + m^2}}} d^3 k $$ from Zee's Quantum Field Theory in a Nutshell. He argues like this: ...
1
vote
3answers
50 views

$N^{1/2}$ and randomness

I apologize if this question is overly vague, but part of the reason I am asking is because I don't know a more precise way of discussing these ideas. To state a general question: What, if any, ...
2
votes
1answer
208 views

Prove or disprove the Big-O of an exponential function

$f(n) = 2^{n+1} = O(2^n)$ Intuitively, I think the statement is false. However, when I go about disproving it, I find that $2^{n+1} = 2^n \cdot 2$, meaning that if there is a constant $C$ larger than ...
0
votes
0answers
36 views

Runtime Complexity | Recursive calculation using Master's Theorem

I have the following recurrence relation (arising from some kind of augmented merge sort): $$ T(n) = T\left({2n\over5}\right) + T\left({3n\over5}\right) + n$$ and I need to find the worst-case ...