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

Asymptotic equivalence and $\lim_{x\to 0} \frac{\sin x}{x}=1$

I know that for $x\sim0$ $\sin x$ can be approximated by $x$, hence they are 'asymptotic equivalent in the neighborhood of $x=0$'. According to the definition of asymptotic equivalence, two ...
2
votes
1answer
145 views

Does $\Theta(m \log n)$ and $0 < m < n^2$ imply $\Theta(n^2 \log n)$?

From a function in $\Theta(m + n^2)$ and $0 < m < n^2$, We conclude it is in $\Theta(n^2)$. Does a function in $\Theta(m\log n)$ so that $0 < m < n^2$, imply that it is in $\Theta(n^2\log ...
0
votes
1answer
6 views

If some function f is in big O(some function g), do f and g necessarily need to have the same domain and codomain?

Say I have a function, $g:\mathbb{R} \mapsto \mathbb{R}$. Then would the set $O(g)$ be defined (as explicitly as possible) as: $$O(g) = \{ f:\mathbb{R} \mapsto \mathbb{R} \space|\space \exists C \in ...
3
votes
3answers
159 views

$x \sim y \implies \log x \sim \log y$?

Does $x \sim y \implies \ln x \sim \ln y$? I would have thought not, but the following has almost persuaded me otherwise: Assume $x \sim y.$ Does this imply that $$\tag{1}I = ...
0
votes
2answers
46 views

Simple equivalent of the rest of the series $\sum\limits_n\frac1{n^3}$

Consider the converging series \begin{equation} \sum_{n\geqslant1}{\frac{1}{n^3}} \end{equation} I want to find an equivalent of the rest : \begin{equation} R_n=\sum_{k=n+1}^{\infty}{\frac{1}{k^3}} ...
0
votes
1answer
37 views

Big O notation for complex-valued functions of a real variable

Let $f,g:\mathbb R\to\mathbb C$. Is there a standard notion of $f = O(g)$? If I had to take a stab at a definition, I'd try something like $f = O(g)$ provided there exists $M>0$ and ...
1
vote
1answer
45 views

Applying the master theorem

State the asymptotic runtime found by the master theorem. If the master theorem does not apply state why: 1) $T(n) = $T($n/3)$ 2) $T(n)= $ $5T$($2n/5$) + $n$ 3) $T(n) = 4T(n/2) +15n^3 + 4n^2 +n+4$ ...
1
vote
1answer
92 views

A limit with $((n-1)!)^{1/(n-1)}$ and other roots of factorials

How to prove that the following limit is positive? $$ \lim_{n \to \infty}\left(((n-1)!)^{1/(n-1)}-2\left(\frac{((n-1)!)^3}{(2n-2)!}\right)^{1/(n-1)}\right) >0,$$ where $ n\in \mathbb Z, n>1 ...
0
votes
1answer
27 views

Asymptotic bounds for the solutions of 3d wave equation

Let $u$ solve the 3-d wave equation: $u_{tt}-\Delta u =0$ such that $u=g$ and $u_t=h$ for $t=0$ and where $g$ and $h$ are both assumed to be compactly supported and smooth. I have shown that there ...
0
votes
1answer
18 views

Why does $f(x) \asymp g(x) \implies log(f(x)) = log(g(x)) + O(1)$?

Why does $f(x) \asymp g(x) \implies log(f(x)) = log(g(x)) + O(1)$? Has it got something to do with the fact that \begin{align} f(x) \asymp g(x) \implies \exists c_1,c_2, \text{ such that}\\ ...
0
votes
1answer
15 views

Show that $\frac{1}{e^\gamma \text{log }x + O(1)} = \frac{1}{e^\gamma\text{log }x} + O\left(\frac{1}{(\text{log }x)^2}\right)$

Show that $\frac{1}{e^\gamma \text{log }x + O(1)} = \frac{1}{e^\gamma\text{log }x} + O\left(\frac{1}{(\text{log }x)^2}\right)$ I'm using one of Merten's estimates in a proof, the one that states ...
1
vote
1answer
26 views

Large $t$ asymptotics of $\int_0^{\infty}\exp(-tx)\exp(-\frac{1}{x^2})dx$

How do I find the asymptotic behavior of $$\int_0^{\infty}\exp(-tx)\exp\left(-\frac{1}{x^2}\right)dx$$ as $t\to\infty$? The Laplace method apparently doesn't work since $\exp(-\frac{1}{x^2})$ isn't ...
1
vote
3answers
40 views

O-Notation: How to put the function in order.

I am new here, so I am sorry for any mistake that I'll probably make. I have an exercise to solve, but I didn't really understand how this really works. I am given the functions $2^n$, $n^{0.01}$, ...
0
votes
1answer
32 views

Meaning of the $\{1 + o(1)\}$

Being a software developer, I have the basic understanding of big-O and small-o notation. But currently I've faced set of mathematical problems, where they operate with asymptotics on much more ...
0
votes
1answer
18 views

Recurence Problem. - Solve either by substitution or Expansion

Function T(n) is defined by the following recurrence relation: $$ T(n)=2T(\lfloor\sqrt{ n}\rfloor)+\log(n) $$ $$ T(0)=1 $$ How would I Solve by substitution and/or Expansion? Note: ...
2
votes
2answers
50 views

Estimating the behavior for large $n$

I want to find how these coefficients increase/decrease as $n$ increases: $$ C_n = \frac{1}{n!} \left[(n+\alpha)^{n-\alpha-\frac{1}{2}}\right]$$ with $\alpha=\frac{1}{br-1}$ and $0\leq b,r \leq 1$. ...
0
votes
2answers
39 views

how long does this subroutine and loop take

Suppose A(.) is a subroutine that takes as input a number in binary, and takes linear time (that is, O(n), where n is the length (in bits) of the number). Consider the following piece of code, which ...
0
votes
1answer
21 views

$g(f(n))\in o(g(n)/n)$ for any $f(n)\in o(n)$

Let $f:\mathbb{N}\rightarrow\mathbb{R}$ be a function such that $f(n)\in o(n)$. Is it always possible to find a function $g:\mathbb{N}\rightarrow\mathbb{R}$ such that $g(f(n))\in o(g(n)/n)$? I'm ...
1
vote
1answer
13 views

$g(n)\in\omega(n^r)$ but $g(f(n))\in o(n^{r-1})$

Let $f:\mathbb{N}\rightarrow\mathbb{R}$ be a function such that $f(n)\in o(n)$. Is it always possible to find a function $g:\mathbb{N}\rightarrow\mathbb{R}$ and a constant $r>1$ such that ...
1
vote
1answer
47 views

Bound for sum of products

Given are $x_1,\ldots, x_n\in \{0,1,\ldots,n\}$, $y_1,\ldots, y_n\in \{0,1,\ldots,n\}$ with the property that $$\sum_{i=1}^{n}{x_i}\leq B,$$ $$\sum_{i=1}^{n}{y_i}\leq B$$ Let's assume that $B$ is ...
0
votes
1answer
26 views

Big-Oh Notation and Solving for f(x)

Taking Discrete Mathematics and completely lost when it comes to Big-Oh Notation. While I know it's used to profile code I can't figure out how to solve the following problem: Find the least integer ...
0
votes
0answers
19 views

asymptotic esimation of a complex integral

I am searching for a general method to evaluate asymptotically this kind of integral $\int_{-\infty}^{\infty}\int_{-\infty}^{\infty}f(q,\omega)\exp[-\mathrm{i}kr]\exp[-\mathrm{i}\omega ...
3
votes
5answers
99 views

When $a\to \infty$, $\sqrt{a^2+4}$ behaves as $a+\frac{2}{a}$?

What does it mean that $\,\,f(a)=\sqrt{a^2+4}\,\,$ behaves as $\,a+\dfrac{2}{a},\,$ as $a\to \infty$? How can this be justified? Thanks.
5
votes
1answer
120 views

Determining a consistent estimator/asymptotic relative efficiency

Question: Let $X_1,\ldots,X_n$ be i.i.d. as $N(0,\sigma^2)$. a) Show that $\delta_1 = k \sum_{i=1}^n |X_i|/n$ is a consistent estimator of $\sigma$ if and only if $ k = \sqrt{\pi/2}$. b) Determine ...
1
vote
1answer
43 views

Prove or disprove: $ \frac{3x^3+2x+1}{x+2} $ is $ \theta (x^2) $.

Prove or disprove: $ \frac{3x^3+2x+1}{x+2} $ is $ \theta (x^2) $. I know that $f(x)$ is $\theta (g(x)) $ if it is both $ O(g(x)) $ and $\Omega (g(x))$ when $ x > n$ I reasoned that $f(x)$ is ...
1
vote
0answers
29 views

BusyBeaver growth: “simple” proof

I just try to prove that $BB(n)$ (BusyBeaver-Function) grows faster than any other computable function. Maybe someone can check the proof? $f(n)$ is a computable function which grows to infinity: ...
2
votes
1answer
71 views

Challenging Algorithms Question: Proving that upper bound for computing 'silhouette' points is nlog(n)

Given a set of points (on the left). The silhouette set of these points is shown to the right. In this problem, all rectangles are defined by two points, $(0, 0)$ and $(x_i, x_j)$. Formally, for a ...
0
votes
1answer
32 views

A Question Regarding Asymptotic Notations

Well, here I am again, stuck with my algorithm's class HW question again... . $g(n) = \Theta(n^2)$, $f(n) = g(n) + g(n-1) + ... + g(2) + f(1)$ Given the conditions above, is it suitable for me to ...
1
vote
1answer
66 views

Help with using Master Theorem on $T(n)=9T(n/3) + \Theta(n^2/\operatorname{lg}(n))$

I want to use the Master theorem to solve the following recurrence. $$T(n)=9T(n/3) + \Theta(n^2/\operatorname{lg}(n))$$ We can easily see that $a=9$ and $b=3$ and $f(n) = n^2/\operatorname{lg}(n)$. ...
1
vote
1answer
16 views

Find functions which change asymptotic properties if raised to 2

Kindly give an example of positive functions f(n) and g(n) such that f(n) = O(g(n)) but it does not hold that 2^f(n) = O(2^g(n)). A friend asked this question as this came in one of his ...
0
votes
2answers
203 views

Arrange the following growth rates in increasing order: $O (n (\log n)^2), O (35^n), O(35n^2 + 11), O(1), O(n \log n)$

I want to Arrange the following growth rates in increasing order This order are following : $O (n (\log n)^2), O ((35)^n), O(35n^2 + 11), O(1), O(n \log n)$ Please give me idea how to arrange growth ...
1
vote
3answers
31 views

For small $z, (1 + z)^{−2} \sim 1 − 2z$…

I came across the following statement while reading Holmes book on Perturbation Methods - To reduce the differential equation, recall that, for small $z, (1 + z)^{−2} \sim 1 − 2z$ I don't know ...
3
votes
0answers
44 views

How can one derive Stokes lines of the Stokes phenomenon of asymptotics from a differential equation?

Is there a standard technique to calculate Stokes lines and anti-Stokes lines of the Stokes phenomenon of asymptotics for a function defined as the general solution to a differential equation without ...
0
votes
1answer
14 views

Asymptotic $T(n)=T(\sqrt{n})+1$

I would like to find the complexity of $T(n)=T(\sqrt{n})+1$ I did : $$T(n)=T(\sqrt{n})+1$$ $$T(n)=T(n^{1/2})+1$$ $$T(n)=(T(n^{1/4})+1)+1=T(n^{1/4})+2$$ And after $k$ steps : ...
0
votes
0answers
14 views

Asymptotic results for functions of order statistics

There are $n$ ($n \ge 3$) iid random variables $\{ {c_i}\} _{i = 1}^n$ on the interval $[\underline c,\bar c]$ ($\underline c>0$). The cdf $F(\cdot)$ and pdf $f(\cdot)$ are unkown to us, but we ...
2
votes
0answers
33 views

Find $f(n)$ in $\binom {2^n} {n^4} = (f(n)+ o(1))^n$

Task is to find $f(n)$ in the following equation: $\binom {2^n} {n^4} = (f(n)+ o(1))^n$ I've found that the problem is a bit over my head. I'm attaching my partial solution below: With use of the ...
2
votes
0answers
55 views

find the the variable that maximizes a function

I have a function that I am trying to find for what input it maximizes. $$ f(n) = {\binom{S}{2}}^{n/S}$$ I need to find the $S$ for which this function maximizes (for infinite $n$). more generally, ...
2
votes
1answer
45 views

terminology relating to o(1)

If someone says, for example, "I have an algorithm that runs in time $n^2+\varepsilon$ for any constant $\varepsilon>0$", the interpretation for this statement seems to be that for any constant ...
3
votes
3answers
47 views

Growth of fraction of products with $\sqrt{n}$ terms

Is the growth of $$f(n):=\dfrac{(n+1)(n+2)\ldots(n+\sqrt{n})}{(n-1)(n-2)\ldots(n-\sqrt{n})}$$ polynomial or not? That is, does there exist constants $k,m$ such that $$f(n)<n^k$$ for all $n>m$?
1
vote
1answer
45 views

Proving n(log(n)) is O(log(n!))

I want to prove $n(\log(n)) \in O(\log(n!))$. I don't really understand how to prove this statement. From the definition, we would have that: $\exists c > 0, \exists N$, so that $\forall n \geq N, ...
0
votes
2answers
46 views

How can I prove that “n is not O(1)”?

I want to prove that $f(n) \neq O(g(n))$ when $f(n) = n$, $g(n) =1$ precisely. I can prove correct big-Oh expression such as $n = O(n)$, $\lg(n) = O(n)$ etc. but I can't prove incorrect big-Oh ...
3
votes
1answer
38 views

Growth of ratio of binomials polynomial or exponential?

Is the growth of $$ \dfrac{\binom{2n}{\sqrt{n}}}{\binom{n}{\sqrt{n}}} $$ polynomial or exponential (or other kind of growth) in $n$? I tried using the Stirling's approximation, which gives ...
6
votes
1answer
202 views

Asymptotic expansion for harmonic sum in two variables

I am interested in determining an asymptotic formula for the double summation of $1/(ab)$, where $a$ is an odd integer ranging between 1 and $k/\sqrt{j}$, $b$ is an odd integer ranging between $a$ and ...
17
votes
1answer
480 views

Double harmonic summation

Let us consider a lattice formed by all points with integer and positive coordinates on a Cartesian plane, and where $K$ is the maximal value for the $x$-axis. Let us assign to each lattice point the ...
1
vote
2answers
38 views

If $f(n) = O(g(n))$ and $f(n) \not\in o(g(n))$, does $f(n) = \Theta(g(n))$?

If $f(n) = O(g(n))$ and $f(n) \not\in o(g(n))$, does $f(n) = \Theta(g(n))$? Well, this is just another algorithm's class HW question, but I don't seem to be able to figure out how to prove or ...
0
votes
1answer
20 views

Suppose that p(x) is any polynomial in x with positive coefficients. Show that log(p(x))∈O(logx).

Suppose that p(x) is any polynomial in x with positive coefficients. Show that $log(p(x))∈O(log\ x)$. My professor posed this question in class today, and I'm not sure how to go about proving it. ...
2
votes
2answers
110 views

Is $f(n) = \mathrm{e}^{o(n)}$ the same as $\,f(n) = o(\mathrm{e}^{n})$?

I have the task for my asymptotics class, which is to state whether $f(n) = e^{o(n)}$ the same as $f(n) = o(e^{n})$. I was assuming that it is, because we can present $f(n)$ as $f(n) = e^{g(n)}$, ...
1
vote
1answer
73 views

Finding the asymptotics of $\sum_{k=1}^n a^k k!$? Note that $a > 0$.

There's no way to use integration method in this case. I also tried to use Stolz–Cesàro theorem, but couldn't find right $y_n$. What method should I use?
2
votes
1answer
56 views

Is there any way to evaluate $e^{H_n} = … + O(\frac{1}{n})$, where $H_n$ is $n$-th harmonic number?

I know, that $H_n = \log n + \gamma + O(1)$, but in that case $e^{H_n} = e^{\log n + \gamma + O(1)} = n e^\gamma e^{O(1)}$ - I can't use this. How can I get this $O(\frac1n)$?
6
votes
3answers
416 views

Is O(n) a proper class or a set?

Is $O(n)$ as the collection of all functions that are bounded above by $n$ a proper class or just a set? What about $O(\infty)$?