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
31 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 ...
4
votes
1answer
104 views

Is $\sum_{k\leqslant n} f'(k)f'(n-k) \asymp f'(n)f(n)$ when $f'$ is positive decreasing?

In this answer of a question of mine, the user Homegrown Tomato gave a nice argument that somewhat shows that $$\int_{\substack{t+s\leqslant x \\ t,s \geqslant 0}} f'(t)f'(s)dtds \asymp ...
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, ...
1
vote
1answer
278 views

Limit involving tetration

Let the notation be $a^{\wedge\wedge}b = \underbrace{a^{a^{\cdot^{\cdot^{a}}}}}_{b\,times}$ for tetration. My mentor conjectured the following: Let $n$ be a positive integer, then let $A(n)$ be ...
3
votes
1answer
36 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
43 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
26 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
25 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
46 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 ...
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
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 ...
2
votes
0answers
24 views

Optimizing an asymptotic recurrence relation with two recursive terms

I have a recurrence relation that looks like this: $T(n) = 2 T(c n) + T((1-c)n) + O(1)$ The base case is just $T(b) = 1$ when $b \leq 1$. I'm trying to figure out the best value of $c \in (0, 1)$ ...
0
votes
4answers
53 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, ...
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 ...
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 ...
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)^{- ...
3
votes
1answer
45 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 ...
2
votes
0answers
33 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 ...
0
votes
0answers
28 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 = ...
1
vote
2answers
66 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
17 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
58 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 ...
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 ...
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 ...
1
vote
2answers
15 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
43 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 ...
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
27 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 ...
0
votes
0answers
17 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 ...
1
vote
3answers
49 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
2answers
43 views

$\int_2^x\frac{dt}{\log^kt}=O\left(\frac{x}{\log^kx}\right)$

I seek to prove the identity $$\int_2^x\frac{dt}{\log^kt}=O\left(\frac{x}{\log^kx}\right)$$ I was given the following hint: Split the integral into $\int_2^{f(x)}+\int_{f(x)}^x$ for a ...
2
votes
2answers
26 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
1answer
41 views

Compute $(\ln(n!))^2$

In a discrete mathematics past paper, I must solve the following problem: We know (from the Stirling approximation) that ...
1
vote
1answer
23 views

Asymptotics of $(\cosh(x+c)-\cosh(c))^{-\frac{1}{2}}$

let $c>0$ be a constant and consider the function $$\frac{1}{\sqrt{\cosh(x+c)-\cosh(c)}}, x>0.$$ I'm wondering how the asymptotic expansion for $x\downarrow 0$ look like!? In case of $c=0$ the ...
0
votes
0answers
12 views

Graphs Approaching Asymptotes

I've been wondering this for a while. For graphs that approach asymptotes, are there certain formulas that can determine the distance between the graph and the asymptote as $x$ gets infinitely small ...
2
votes
0answers
24 views

Approximation of Hermite functions

I'm looking for an "easy" proof of the asymptotic expansion of Hermite functions ($f_n(x)=H_n(x)e^{-x^2/2}$ where $H_n$ is the Hermite polynomials). The asymptotic expansion is $$ f_n(x) \sim_{n ...
0
votes
0answers
35 views

How to asses the order of combinations

Let $\{a_i\}_{i=1}^m$ be some increasing sequence, bounded away from zero. How to see that as $n\to\infty$, we obtain $$\begin{pmatrix} n\\ m \end{pmatrix}^{-1}\sum_{i=1}^m\begin{pmatrix} ...
1
vote
0answers
35 views

Two-term asymptotic approximation for roots of a polynomial (dominant balance)

I'm trying to find the roots to the following equation: $t^5 - \epsilon t^3 + \epsilon^3 = 0$ as $\epsilon \rightarrow 0$. From expansion $t= \epsilon^{\alpha}t_1 + \epsilon^{2\alpha}t_2 + ...
0
votes
1answer
16 views

$ n - \sqrt{n}$ $\Theta$ Complexity

$ n - \sqrt{n} \leq n - \sqrt{n} + \sqrt{n}=n=O(n)$ But I don't know what I should do about $\Omega(.) , \Theta(.)$ Should I try to solve it with lim?
0
votes
0answers
14 views

Additive error in Stirling's Approximation

I know that Stirling's Approximation is asymptotic to $n!$ as in the ratio approaches $1$ (which is the definition). But as far as I have noticed, the additive error diverges. Is this a common ...