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

learn more… | top users | synonyms (1)

0
votes
0answers
7 views

A Question from Murray - Asymptotic Analysis

I'm stuck on one of the questions related to the method of stationary phase in Murray's book on Asymptotic analysis. The question is as follows; If $h(t)$ has a single stationary point at $t_0$, ...
0
votes
0answers
17 views

Big $O$ question for While and For loops [on hold]

I have to find the exact $O(N)$ for these instructions, not just the order of magnitude. I'm not getting any of the answers provided for me. I know the first loop is $O(3N+2)$. The declaration of ...
1
vote
3answers
105 views

how to prove $\sum_{i=1}^n i^k =\Theta(n^{k+1})$

we can say that if all $i$ s in the sum were equal to $n$ then the answer to the summation would be $n\cdot n^k$. So $n^{k+1}$ is the upper bound.so $\displaystyle\sum_{i=1}^n i^k=O(n^{k+1})$ For ...
-1
votes
2answers
18 views

Arrange the following growth rates in increasing order O((35)^n),O(n^4),O(1),O(n^3 logn) [duplicate]

I want to Arrange the following growth rates in increasing order This order are following : O((35)^n),O(n^4),O(1),O(n^3 logn) Please give me idea how to arrange growth rates in increasing order
0
votes
0answers
29 views

Understanding $\Theta$-notation rigorously

Let $f$ and $g$ be functions on $\mathbb{N}$. If $f(n) \in \Theta(g(n))$, we say that (for sufficiently large input) "the function $f(n)$ is equal to $g(n)$ to within a constant factor". What does ...
0
votes
0answers
25 views

Name for kind of big O notation with leading coefficient

Context: As known the big O notation $O(f(n))$ describes a function $g(n)$ such that there is a constant $C \ge 0$ with $\limsup_{n\to\infty} \left|\frac{g(n)}{f(n)}\right| \le C$ (I assume that ...
-1
votes
1answer
26 views

Show that $f(n)$ is $O(g(n))$ then $f(n)+c$ is $O(g(n))$ [on hold]

Show that $f(n)$ is $O(g(n))$ then $f(n)+c$ is $O(g(n))$ for all constants $c$. In our class, $$O(g(n)) = \{f(n) \mid \exists C,n_0 \colon \forall n \geq n_0 \colon |f(n)| \le C|g(n)| \}$$
7
votes
0answers
266 views

Entropy of matrix vector product

Consider a random $n$ by $n$ circulant matrix $M$ whose first row entries are chosen independently and uniformly from $\{0,1\}$. Let $M'$ be the $m$ by $n$ matrix which is formed by taking the first ...
1
vote
3answers
35 views

$O( n^3)$ vs $O(n^2 \ log n)$

I was wondering how $n^3$ compares to $2n^2 \log n$ as I thought that $n^3$ is $\Omega(n^2 \log n)$ but there is the fact that $n$ is $O(n \log n)$ so I wasn't sure whether it is bigO or $\Omega$
0
votes
1answer
32 views

What is the big Oh notation for the following series.

I have the series $1+3+9+27+... + 3^n$ . I need to find the Big O solution. What I have tried. The above series is a Geometric Progression with r=3. SO the sum would be. $ [1* 3^{n+1} - 1]/2 $ How ...
1
vote
0answers
14 views

asymptotic of an interesting recurrence realtion (more general case)

A link to the original question for reference:Click here I tried to study a more general situation: Let $y_{d,d}=1$ and $$ ...
0
votes
1answer
50 views

Simplifying $f(x) = \left(x^{3} + 2x^{2} + O(x)\right)\cdot\left(1 + \frac{1}{x} + O\left(\frac{1}{x^{2}}\right)\right) $

Simplify $$f(x) = \Big(x^{3} + 2x^{2} + O(x)\Big)⋅\Bigg(1 + \frac{1}{x} + O\bigg(\frac{1}{x^{2}}\bigg)\Bigg) $$ as $x \to +\infty$. I am a bit stuck as to what to do with the three sets of ...
4
votes
1answer
60 views

Each number in $S\subseteq \{1,\ldots,2n\}$ does not divide another one, with $|S|= n$. In how many ways?

Let $f(n)$ be the number of subsets $S\subseteq \{1,2,\ldots,2n\}$ such that $|S|=n$ and $a$ does not divide $b$ whenever $a,b \in S$ are distinct. Can we evaluate $f(n)$, at least asimptotically? ...
0
votes
0answers
16 views

Comparing functions

I wanted to make sure I had the correct understanding of the following big $O/\Theta/\Omega$ questions and I figured it would be better posted here than SO as it was more about comparing function. a) ...
0
votes
0answers
13 views

“Asymptotic” $\mathbb{R}$-algebras

Definition. By an asymptotic $\mathbb{R}$-algebra, I mean an $\mathbb{R}$-algebra $F$ of functions $\mathbb{R} \rightarrow \mathbb{R}$ satisfying: $$\mathop{\forall}_{f:F}\left[\left(\lim_{x ...
0
votes
0answers
18 views

What do we call the number that measures how good of an asymptote $g$ is to $f$, and what are the basic results about this number?

Suppose we have a (potentially very complicated) smooth function $f : \mathbb{R} \rightarrow \mathbb{R},$ and we're trying to approximate it (in the limit as the input value goes to $+\infty$) by a ...
1
vote
1answer
18 views

Large pairwise coprime sets

Say that a set $S\subseteq\Bbb N$ is pairwise coprime if every two elements of $S$ are relatively prime. Denote by $f(n)$ the size of a maximal pairwise coprime subset of $\{1,...,n\}$. What is ...
1
vote
1answer
21 views

Product property of Big O

Trying to prove: If $f(n)$ and $g(n)$ are both $O(h(n))$, then $f(n)*g(n)$ is $O(h^2(n))$. Understanding so far : The product of upper bounds of functions gives an upper bound for the product of ...
0
votes
1answer
19 views

Asymptotic error expansion of global error for single step methods

My question refers to the proof of the following theorem, but it may suffice to just skip the theorem and continue with the problematic taylor expansion $(\ast)$: Let $f(t,y)$ and the single step ...
18
votes
7answers
4k views

Stirling's formula: proof?

Suppose we want to show that $$ n! \sim \sqrt{2 \pi} n^{n+(1/2)}e^{-n}$$ Instead we could show that $$\lim_{n \to \infty} \frac{n!}{n^{n+(1/2)}e^{-n}} = C$$ where $C$ is a constant. Maybe $C = ...
7
votes
0answers
104 views

Counting the size of the largest sets of independent strings

This question derives from a PPCG coding challenge I posed previously. For a given positive integer $n$, consider all binary strings of length $2n-1$. For a given string $S$, let $L$ be an array of ...
0
votes
2answers
47 views

How to show that $O(n^\frac{3}{4} \log n) = O(n)$?

I try to analyze LazySelect algorithm (finds kth order statistic of a set). One of the steps is to take a sample of $n^\frac{3}{4}$ elements and sort it. It seems like this sorting is linear relative ...
2
votes
1answer
30 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
3answers
103 views

Solve the recurrence $T(n) = 2T(n-1)+n^2$

Solve the recurrence $$T(1) = 1, T(2) = 1, T(3) = 1,T(n) = 2T(n-1)+n^2, n > 3$$ I have now, $$T(n) = 2T(n-1)+^2 $$ $$= 2(2T(n-2)+(n-1)^2+n^2$$ $$=4T(n-2)+2(n-1)^2+n^2$$ $$....$$ ...
6
votes
1answer
174 views

The asymptotic of the number of integers that are sums of three nonnegative cubes

Let $c(n) $ be the number of distinct integers between $0 $ and $n $ of the form $ a^3 + b^3 + c^3$, meaning the sum of $3$ nonnegative cubes. $C(n) = O( n \space \ln(n)^x ) $ Find and prove the ...
2
votes
0answers
59 views

Arithmetic progression of squarefree integers?

Let $x$ be a given positive integer. I'm intrested in the longest arithmetic progression of squarefree integers within the interval $(x,x^2)$. Both constructive and nonconstructive results. For ...
1
vote
2answers
57 views

Why is $\binom{2n}{n} \asymp \Theta \big(\frac{2^{2n}}{\sqrt{n}}\big)$?

I saw this statement : $$\binom{2n}{n} \asymp \Theta \bigg(\frac{2^{2n}}{\sqrt{n}}\bigg) \asymp \Theta\bigg(\frac{4^n}{\sqrt{n}}\bigg)$$ How did we go from the first statement to the second? I tried ...
2
votes
1answer
40 views

Estimate integral $\,\displaystyle\int_{0}^{\infty}\operatorname{sech}\left(\varepsilon x\right)\cos\left(kx\right)\,dx,\,$ with $\,k,\varepsilon>0$

$ \newcommand{\sech}{\operatorname{sech}} $ Is there any analytic/asymptotic way to estimate the value of the integral: $$ \int_{0}^{\infty} \sech\left(\varepsilon x\right)\cdot ...
1
vote
3answers
72 views

Missing steps: Show the sum of the first n positive integers is of order $n^2$

In Rowsen's Discrete Mathematics text, 6th edition. He has this problem as an example (#11) on page 190. His solution for obtaining a lower bound is to ignore the first half of the terms. He does the ...
1
vote
0answers
15 views

what happens when expansion parameter is of the order of dynamical variable itself?

Lets consider following differential equation, $\epsilon \frac{dy}{dt} = ....$ In principle one can use Method of matched asymptotic expansion or Method of multiple scales to solve such singular ...
2
votes
2answers
29 views

Asymptotic of $ \sum_{r=1}^{k} \frac1{r^{3/2}}$ - Generalized Harmonic Number

What is the asymptotic approximation of the following generalized Harmonic number as $k \to \infty$ ? $$H(1.5,k) = \sum_{r=1}^{r=k} \frac{1}{r^{1.5}}$$ (there is a similar question posted on ...
3
votes
1answer
64 views

Does writing $f(x)\sim \ell$ have a sense?

If $\lim_{x\to a}f(x)=\ell$, is it correct to say that $f(x)\sim_a \ell$ ? I would say yes since $\lim_{x\to a}\frac{f(x)}{f(a)}=1$, but on a test I wrote $e^{-t}\sim_0 1$ and the corrector said that ...
2
votes
0answers
50 views

Approximate an integral with Bessel functions

Given $r,a,\lambda\in\mathbb{R}$, $r<a$, how can I find an approximate solution for the following definite integral? $$ \int_0^\infty J_0 (\lambda r)J_1(\lambda a)\frac{1}{\sqrt{n+\lambda^2 ...
-2
votes
2answers
30 views

specifying an asymptotic function

Please help me out; I need to specify a function satisfying these conditions: $$ f(0)=1 \;\;;\;\lim_{x \to \infty}f(x)=0$$ Hopefully does there exist a simple answer? Thanks a lot!
1
vote
2answers
34 views

oblique asymptote problem

I can't resolve limit for oblique asymptote for: $$\frac{2x^2 e^{1/x}}{2x+1}-x$$ I've tried solving it by putting the common denominator but it's a bit confusing because the numerator is bigger then ...
0
votes
0answers
23 views

Simple question about asymptotic notation

I'm quiet new to the asymptotic world, so apology in advance if this question seems too trivial for you experts. Given $\frac{2kn2^{-k}}{E[X]}.$ As $k \sim 2\text{log}_{2} n$, the numerator is ...
11
votes
1answer
120 views

Asymptotic Behavior of a Sum with Binomial Coefficients

The Problem: Find the asymptotic behavior (with respect to $n$) of the following sum $$\sum\limits_{j = 3}^n \binom{n}{j} \frac{(j - 1)!}{2\cdot n^j}. $$ Where the Problem Comes From: If we ...
3
votes
1answer
59 views

Calulate a limit involving $\zeta{(\zeta{(z)})}$

I'm currently trying to evaluate the following limit: $$ \lambda=\lim_{z\to\infty}{\left[2^z-\left(\frac{4}{3}\right)^z-\zeta{(\zeta{(z)})}\right]} $$ A look at numerical approximations suggests, that ...
-4
votes
2answers
81 views

Find witnesses proving that $f(x) = 2x^3 + x^2 + 5$ is $O(x^3 )$. [closed]

Find witnesses proving that $f(x) = 2x^3 + x^2 + 5 \textrm{ is } \mathrm{O}(x^3 )$. What do i need to do here? Like step by step?
0
votes
0answers
41 views

For any arithmetic progression $n \in \Bbb{N} : n \equiv b \pmod a$, the natural density is $\frac{1}{a}$?

This question comes from here (page 10). Given that $d(A) := \lim_{x\to\infty}\frac{1}{x}\sharp\{n \leq x : n \in A\}$, how do I get that: 1) $d(n \equiv b \pmod a) = \lim_{x\to\infty}(\left [ ...
-2
votes
0answers
50 views

BIG OH:$ f (x) = 3x^3 + 2x + 4$. One has

I have this question in my homework. Its an a multiple choice question and goes as following: Let $f (x) = 3x^3 + 2x + 4$. One has that $O(x^3)$ ** the answers have been checked with the teachers ...
0
votes
0answers
29 views

How to prove $x^m = O(e^x)$ for any $m \gt 0$?

My attempt: It's true for $m = 1$ clearly. Now assume true for $m=1\dots M-1$. Then $x = O(e^x)$ and $x^{M-1} = O(e^{M-1})$. Lemma: if $f = O(g)$ and $f' = O(g')$ then $ff' = O(gg')$. Proof: $f = ...
1
vote
2answers
31 views

Simple question, what is meant by 'as $x \to \infty$ the number of squares $\leq x$ is $\sqrt{x} + O(1)$?

For $x \to \infty$: the number of squares $n^2 \leq x$ is $\sqrt{x} + O(1)$. From here (page 6). More specifically, do they mean that... I'm confused now. I'm really not sure what they mean ...
3
votes
1answer
33 views

$\sum_{n \leq x} \frac{1}{n} = \int_{1}^x \frac{dt}{t} + O(1)$ help deriving it

On page 5 of: Probabilistic Number Theory by Dr.J¨orn Steuding, there's $\sum_{n=2}^{[x]} \frac{1}{n} \lt \int_{1}^{[x]} \frac{dt}{t} \lt \sum_{n=1}^{[x] - 1}$ Therefore integration yields: ...
1
vote
1answer
124 views

Can Cauchy theorem be applied to $\log{(z)}e^{ixz}$?

I'm reading about asymptotic analysis on the integral $I(x)=\int_0^1{\ln{t}e^{ixt}}dt$. The book tells me that I can use Cauchy theorem to deform the contour into a rectangular contour: $0 \to iT \to ...
0
votes
0answers
24 views

The function $g(x)$ is in $\Omega(x^c)$ as $x\rightarrow 0$ for all $c>0$. Does this imply that $\lim \inf_{x\rightarrow 0} g(x) > 0$?

Consider a function $g: \: \mathbb R^+ \mapsto \mathbb R^+ $. For any $c>0$ this function is in $\Omega(x^c)$ as $x\rightarrow 0$. That is, given $c>0$ there exist $L$ and $x_0$ such that $g(x) ...
3
votes
1answer
907 views

Little 'o' / Big 'O' Definitions

I understand, or at least think I understand, the nature of a function that is "little o": If $f$ is a function between Banach spaces E and F, then it is "little-o" if $$|x|\rightarrow 0 \implies ...
5
votes
3answers
9k views

Family of functions with two horizontal asymptotes

I'm looking for the equation of a family of functions that roughly resembles the sketch below (with apologies for the crudeness of said sketch):     Properties I'm looking for: ...
7
votes
0answers
98 views

Bear of an integral

I have a pretty ferocious integral to solve, and would be over the moon if I were able to get some sort of analytic expression / insight for it. $$ I = \int_{r}^{\infty} r_0^{-5/2} W_{-i\alpha'/2, ...
10
votes
1answer
76 views

Asymptotic behaviour of log log sum

I am interested in the asymptotics of $$F(m) := \prod_{j=1}^m \log(j+1) = \exp\left(\sum_{j=1}^m \log \log(j+1) \right)$$ Is there anything known? If not I figure I will need some good bounds on the ...