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

learn more… | top users | synonyms (1)

9
votes
1answer
91 views

An upper bound for Summative Fission numbers

I recently found OEIS entry A256504 and have been playing around with this sequence a bit. Its definition is: For a positive integer $n$, find the greatest number of consecutive positive integers ...
5
votes
2answers
107 views

How to get the asymptotic form of this oscilatting integral?

So the integral is like this: $$\int_1^\infty \frac{\cos xt}{(x^2-1)\left[\left(\ln\left|\frac{1-x}{1+x}\right|\right)^2+\pi^2\right]}\mathrm{d}x$$ The question is how to get the asymptotic form of ...
2
votes
1answer
44 views

Show that $f(x) = O(1/x)$

Let $f:\mathbb{R}\to\mathbb{R}$ such that $f\ge 0$, monotonically decreasing and $\int_0^\infty f(x) \ dx < \infty$. Prove that $f(x) = O(1/x)$. So basically, both $f(x)$ and $1/x$ are ...
1
vote
2answers
60 views

Divide and Conquer in big O notation

I've got a problem – divide-and-conquer part of my program divided my problem into 2 parts: 1/7 and 5/7 of a problem + merging in a linear time. I need to know it's asymptotic complexity. I know, it ...
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 ...
6
votes
0answers
43 views

Comparing asymptotic forms of series

I've run into some asymptotic analysis in research here and there and largely it feels pretty magical to me. My research has led me to consider the following question which I haven't the slightest ...
1
vote
0answers
35 views

Hamming weight in multiple label

Assume you have a $N$ balls. You give each ball $T$ different labels randomly from $\{0,\dots, N-1\}$. So hamming weight of each of labelling varies from $0$ to $\lceil\log_2 N\rceil$. What is ...
-1
votes
2answers
42 views

How to solve recurrence equation with logarithms using the Master Theorem

how do you solve this equation of recurrence? $T(1) = 1$ $T(n) = 2T(\frac{n}{3})+n*log_2(n)+1$ The problem is the term $n*log_2(n)$. Can I only consider only $n$ as it's the larger then $log_(n)$ ...
0
votes
0answers
11 views

Finding the correct asymptotic functions

in an exercise of algorithms, I have to find a function $f(n)$ that is $Ω(n^2)$ and such that for every $n>0$ is $f(n)<n^2$. I also need to find a function $g(n)$ which is $Ω(n^2)$ but not ...
3
votes
1answer
23 views

Find the asymptotic behavior of solutions of the equation

Find the asymptotic behavior of solutions $y$ of the equation $$x^5 + x^2y^2=y^6,$$ which tends to $0$ when $x$ tends to $0$. My solution: if $y=Ax^n$, then $$x^5 + A^2x^{2+2n}=A^6x^{6n}.$$ If ...
2
votes
1answer
21 views

True or false. If $f(n) = \Theta(n^2)$ and $g(n) = \Theta(n^2)$ then $(f-g)(n) =\Theta(n^4)$ where we define $(f-g)(n)=f(n)-g(n) \forall n$.

True or false. If $f(n) = \Theta(n^2)$ and $g(n) = \Theta(n^2)$ then $(f-g)(n) =\Theta(n^4)$ where we define $(f-g)(n)=f(n)-g(n) \forall n$. I believe this is false. Take $f(n) = 4n^2, g(n) = ...
0
votes
2answers
46 views

How to prove order of equation using Big-Oh notation? [closed]

How can I prove this order equation using Big-Oh notation? $$O(3n^3+2n^2+5) = n^3$$
5
votes
1answer
201 views

How to prove this inequality $\pi(x) > \log x - 1$ involving the prime counting function?

Problem Prove that $\pi(x) > \log x - 1$. Progress Based on a hint and very elementary methods, I got that $$ \prod_{p \leq x} (1-p^{-1})^{-1} \leq \prod_{k=2}^{\pi(x)+1} (1-k^{-1})^{-1}. $$ The ...
2
votes
1answer
36 views

Finer asymptotic estimate of an integral

I'm studying the asymptotic behaviour for large $n\in \mathbb N$ of $\displaystyle \int_1^\infty \frac{1}{1+t^{n+1}}$ Using the substitution $u=(n+1)\ln(t)$, $$\displaystyle \int_1^\infty ...
0
votes
1answer
45 views

Prove that $2^{n+1} = \Theta(2^n)$?

I need to prove that $2^{n+1} = \Theta(2^n)$? To do this, I need to show that there are positive constants $c_1,c_2$ such that $$c_1 2^n \le 2^{n + 1} \le c_2 2^n$$ ...for all sufficiently large ...
0
votes
1answer
42 views

Disprove $f(n) = 2^{2n}$ is $O(2^n)$

Disprove $f(n) = 2^{2n}$ is $O(2^n)$ Informally I know that this means we have to show that $2^{2n}$ grows much faster than $2^n$. More formally, I know that we need to show that for any $N$, ...
0
votes
0answers
27 views

What is the difference between “DTIME” and “Big O” notation?

I have some understanding of "big O" and "little O" notation. I have heard of "DTIME" but have not had formal education or training regarding its use. Can someone explain the difference (or ...
0
votes
1answer
47 views

Asymptotic sums and liminf

Given an arithmetic function $f(n)>0$ with $$\liminf \frac{g(n)}{f(n)}=C$$ for a certain constant $C$ and another function $g(n)>0$, in the study of the asymptotic bound for $$ \sum_{n\leq x} ...
0
votes
0answers
52 views

Solving the recurrence $T(n) = 5T(n/7) +\log n$

I am trying to solve the recurrence $T(n) = 5T(n/7) +\log n$ to find the complexity of an algorithm. Although I solve this immediately with the Master Theorem if I try to solve the recursion I found ...
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 ...
18
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
37 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 ...
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 ...
3
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
203 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
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, ...
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
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 ...
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
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 = ...
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
34 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
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 ...
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 ...