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

learn more… | top users | synonyms (1)

1
vote
1answer
50 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
27 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
21 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
102 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
125 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
44 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
30 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
74 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
35 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
70 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
17 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
358 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
52 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
18 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
18 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
57 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
48 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
48 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
46 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
49 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
40 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
211 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
491 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 ...
0
votes
1answer
21 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
112 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
74 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
59 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
418 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)$?
1
vote
0answers
64 views

Big-O estimate (smallest order)

I'm trying to give a big-O estimate for each of these functions, where I want to use a simple function $g$ of smallest order. I have them all done I just wanted to someone to run through and check ...
1
vote
3answers
34 views

Asymptotic behavior of $-gTt-gT^2e^{\frac{-t}{T}}$ for small $t$

I want to solve this using Taylor series expansion of $e^{f(x)}$ $$\begin{align}x=-gTt-gT^2e^{\frac{-t}{T}}+gT^2+x_0\end{align}$$ Show that for small values of t $(t\ll T)$, the equation for ...
1
vote
1answer
57 views

Show that $(1 + \mathcal{O}(\epsilon))(1 + \mathcal{O}(\epsilon)) = (1 + \mathcal{O}(\epsilon)) . $

Show that $(1 + \mathcal{O}(\epsilon))(1 + \mathcal{O}(\epsilon)) = (1 + \mathcal{O}(\epsilon)) . $ The precise meaning of this statement is that if $f$ is a function satisfying $f(\epsilon) = (1 ...
1
vote
0answers
52 views

Asymptotics of expectation of a ratio of binomially distributed random variables

Let $X_n \sim Bin(n_1,p_1)$ and $Y_n \sim Bin(n_2, p_2)$ with $n_1 + n_2 = n$ and $p_1,p_2 >0$ be independent, binomially distributed random variables. We furthermore assume that $\frac{n_1}{n} \to ...
0
votes
0answers
33 views

What does the constant “C” in Big-O notation represent in reality?

My textbook shows a definition in the section for learning Big-O Notation: $|f(x)| \le C |g(x)|$ What does the C represent in reality so that I can understand this better? I am assuming that C at 1 ...
4
votes
2answers
90 views

Can someone explain the mathematical definition of BigO?

I am learning about Big O notation for my Comp Sci class and my instructor provided the following definition: Questions: 1) What does it mean for $f(n) = \mathcal{O}(g(n))$? I understand how ...
0
votes
1answer
54 views

How to differentiate an expression involving big-o notation?

From Apostol - Introduction to analytic number theory (Theorem 3.3) we have $$ x\geq1, \sum_{n\leq x}d(n)=x\log x+(2\gamma-1)x+O(\sqrt{x}):=E(x), $$ I want to differentiate $E$ -- to get a rough ...
1
vote
2answers
37 views

Solving (for asymptotics) of certain recurrence equations.

I am thinking of examples of the kind where the function occurs multiple times on the R.H.S with different arguments. This is the case where most techniques I know don't seem to work. For example ...
1
vote
1answer
25 views

correcting an invalid binary heap in $\Theta (n)$

We are given a binary max (every node is larger than its children) heap with $n$ elements. We now change $\frac{n}{4}$ of the elements at random. We don't know which ones and to which value. And so, ...
0
votes
2answers
81 views

Any power of logarithm is $O(N)$

This is more of a computer science question but it uses calculus and proof techniques so I think it might be more appropriate here. Basically, how do I prove that, for any constant $K \geq 1$, ...
0
votes
1answer
62 views

Disproving Big O Statements

Show that $2^{\sqrt{n}}$ is not $O(n^{10})$ from the definition of $O()$. I'm not sure on how to start this problem. From the definition, if we want to prove such an statement, then $\forall ...
0
votes
1answer
25 views

Inequality in the limit

Given that we have the following conditions: $f = O(\delta)$, $g = O(\delta^2)$, $f > 0, \delta > 0$, can we conclude that as $\delta \to 0^+$, $f+g>0$?
2
votes
2answers
53 views

Big-O Function for f(x)

I'm currently taking a Discrete Mathematics course which just started the chapter on The Growth of Functions. A (very) brief overview was given in lecture that covered the Big-O definition. Let ...
2
votes
4answers
65 views

Prove that $3^n$ is not $O(2^n)$.

I am working on some Big oh questions and I can't seem to get how disprove them. In this case we have: Prove that $3^n$ is not $O(2^n)$ I can see that its obvious just by looking at the two ...
4
votes
5answers
5k views

Big-O Notation - Prove that $n^2 + 2n + 3$ is $\mathcal O(n^2)$

I'm taking a course in Discrete Mathematics this summer, and my book doesn't offer a very good explanation of Big-O notation. I understand that if $f(x)$ is $\mathcal O(g(x))$ it means that there ...
1
vote
2answers
43 views

Prove $f(n)=O(n^2)$

I have to prove that the function $f(n)=3n^2-n+4$ is $O(n^2)$. So I use the definition of big oh: $f(n)$ is big oh $g(n)$ if there exist an integer $n_0$ and a constant $c>0$ such that for all ...
0
votes
2answers
40 views

Is it true that $|O(2n) - O(n)|=O(n)$?

I need to prove or contradict:$$|O(2n) - O(n)|=O(n)$$ I try: $$\\f(n)=1.5n\in O(2n),g(n)=0.25n\in O(n),h(n)>0\in O(n) : \\ |1.5n - 0.25n|=h(n)\\1.h(n)=1.25n \in O(n)\\ but: 2. h(n)=-1.25n \notin ...
0
votes
1answer
27 views

Show running time of algorithm on input of size n is $\Omega$ (f(n))

Basically I'm given this algorithm where I have an array A of integers which outputs an n-by-n array B where B[i,j] contains the sum of the array entries A and asked to give a bound of the form ...
2
votes
1answer
73 views

Asymptotic Function proof?

I am doing questions from past exams and I stumbled upon this one. I have no idea how to go about solving it.I never had any logarithmic functions in my previous bigOh proofs nor have I had to use ...
0
votes
1answer
50 views

Why does $f(n) = O(n^2)$?

My book says: For example, consider $f_1(n) = n$ and $f_2(n) = n^2+1$. Clearly, the former is $O(n^2)$ and the latter is $O(n^3)$. I thought they would both be $O(n)$ and $O(n^2)$ respectively. ...