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
14 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 ...
0
votes
1answer
37 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 ...
13
votes
4answers
352 views

Infinite Sum of Sines With Increasing Period

A while ago, I was thinking about the Weierstrass function, which is a sum of sines with increasing frequencies in such a way that the curve is a fractal. However, I wondered what would happen if one ...
1
vote
3answers
94 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}$, ...
9
votes
2answers
337 views

An asymptotic expression of sum of powers of binomial coefficients.

Let $k$ be a fixed positive number and $n$ an integer increasing to infinity. Then $$\sum_{\nu =0}^n \binom{n}{\nu}^k \sim \frac{2^{kn}}{\sqrt{k}} \left( \frac{2}{\pi n} \right)^{\frac{k-1}{2}}.$$ ...
3
votes
5answers
103 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.
1
vote
1answer
56 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 ...
2
votes
1answer
171 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 ...
2
votes
1answer
103 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 ...
1
vote
1answer
192 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)$. ...
0
votes
1answer
171 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
19 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 ...
1
vote
3answers
34 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 ...
1
vote
2answers
106 views

Growth of $\sum_{x=1}^{n-1} \left\lceil n-\sqrt{n^{2}-x^{2} } \right\rceil$

I'm interested in the growth of $$f(n):=\sum_{x=1}^{n-1} \left\lceil n-\sqrt{n^{2}-x^{2} } \right\rceil \quad \text{for}\quad n\rightarrow\infty $$ Progress (From comments) I've got ...
3
votes
0answers
224 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
41 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 : ...
1
vote
2answers
184 views

Efficiently calculating the 'prime-power sum' of a number.

Let $n$ be a positive integer with prime factorization $p_1^{e_1}p_2^{e_2}\cdots p_m^{e_m}$. Is there an 'efficient' way to calculate the sum $e_1+e_2+\cdots +e_m$? I could always run a brute ...
1
vote
0answers
32 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
36 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
1answer
51 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 ...
5
votes
1answer
188 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 ...
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
87 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
75 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
55 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 ...
1
vote
1answer
85 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 ...
1
vote
0answers
39 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: ...
3
votes
1answer
121 views

How to find asymptotics of this sum

Is there any way to find $f(n)$ in this term: $$\sum_{k=2}^n \frac1{\ln \ln(k!^{k!})} \sim f(n)?$$ The tilde symbol means that $$\lim_{n\to∞} \frac{f(n)}{\sum_{k=2}^n \frac1{\ln \ln(k!^{k!})}} = 1$$ ...
0
votes
1answer
38 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. ...
1
vote
1answer
85 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
76 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
429 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
124 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 ...
3
votes
2answers
130 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)}$, ...
2
votes
1answer
77 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
86 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 ...
4
votes
2answers
154 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 ...
1
vote
0answers
58 views

Cumulative minimum of an Ornstein-Uhlenbeck process

Assume we generate a sample path $X_t$ from an Ornstein-Uhlenbeck distribution (i.e. a mean-reverting random walk), where $dX_t = −\rho(X_t − \mu)dt + \sigma dW_t$. For concreteness, take $\mu = 0$, ...
0
votes
1answer
260 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 ...
1
vote
1answer
30 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
91 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
28 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$?
1
vote
2answers
4k 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 ...
2
votes
2answers
380 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 ...
1
vote
2answers
48 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 ...
1
vote
2answers
887 views

How to solve the recurrence relation for tight asymptotic bound without using master theorem?

I have the following recurrence in my problem: $$T(n)= 4T(n/2)+n.$$ I have solved it by substitution by assuming the upper bound $O(n^3)$ but in solving it for $O(n^2)$ i am having some problems.I ...
0
votes
1answer
137 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
3answers
57 views

How can you tell if you an algorithm has running time of $\log n$?

I would like an example of an algorithm (or pseudocode) that shows $\log n$ running time. I know what $n$ and $n^k$ running time looks like (simple nested loops) but what does $\log n$ look like and ...
2
votes
1answer
96 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
56 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. ...