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

learn more… | top users | synonyms (1)

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 : ...
1
vote
2answers
49 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 ...
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
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 ...
5
votes
1answer
119 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
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 ...
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 ...
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: ...
3
votes
1answer
87 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
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. ...
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)$?
1
vote
0answers
59 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 ...
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
55 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
50 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
86 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
0answers
13 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
56 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
23 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
80 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
24 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$?
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 ...
2
votes
2answers
41 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
39 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
108 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
25 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 ...
0
votes
2answers
25 views

How can you tell if you a piece of code has running time of logn?

I'm new to Data Structures and Algorithms and I would like an example of code (preferably java or any pseudocode) that shows logn running time. I know what n and n^k running time looks like (simple ...
2
votes
1answer
70 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
49 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. ...
1
vote
1answer
131 views

Proving Big O as lim f(n)/g(n) = 0

We have to prove that if $lim_{(n\rightarrow\infty)} \frac{f(n)}{g(n)} = 0$, then $f(n)$ is $O(g(n))$ but $g(n)$ is not $O(f(n))$. I understand that because the limit is 0, then it can be said that ...
0
votes
3answers
70 views

Prove that $1^{k} + 2^{k} + \cdots + n^{k}$ is $O (n^{k+1})$

I have the following to prove: $1^{k} + 2^{k} + \cdots + n^{k} \text{ is }O (n^{k+1})$ I have done the following: $$\frac {1^{k} + 2^{k} + \cdots + n^{k}}{n^k} \leq n$$ Am I on the right track? I ...
2
votes
4answers
63 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 ...
1
vote
1answer
61 views

Onion-peeling in O(n^2) time

I am working on the Onion-peeling problem, which is: given a number of points, return the amount of onion peels. For example, the one below has 5 onion peels. At a high level pseudo-code, it is ...
2
votes
0answers
31 views

Prove the big theta

I need to find a $n_0$ and $k$ for Big Oh and an $n_0$ and $k$ for Big Omega, to find a big theta bound for: $5n^2 - 9n = \theta(n^2)$ Can anyone help me and show me how to find these for this ...
1
vote
3answers
33 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 ...
0
votes
1answer
66 views

Big Theta Proof Tightness

I found that $n_0 = 1 $ and $k=5$ for Big Oh, but I am somewhat confused on how to prove big omega as I have a negative sign in my expression. Furthermore by showing big oh and big omega, am I showing ...
0
votes
1answer
19 views

Comparing algorithmic complexities

If an algorithm has a running time $ T(n) = O(n$ log $n)$, would it be possible to show that $T(n) = o(n^2)$?
1
vote
1answer
26 views

Taking the log of both sides to determine big Theta/Omega/O

I've managed to confuse myself over this detail: Obviously: $n^2 \notin \Theta(n)$ Now if we take the $\log$ of both sides, we get: $$\log(n^2) \leq \log(cn)$$ $$2\log(n) \leq \log(c) + \log(n)$$ ...
3
votes
1answer
32 views

If $f$ is equal to an affine function up to $1$-th order at $a$, then $f$ is differentiable at $a$, proof more subtle then it appears?

I came across the following exercise: Two functions $f, g : \mathbb R \to \mathbb R$ are equal up to $n$th order at $a$ if $$ \lim_{h \to 0} \frac{f(a + h) - g(a + h)}{h^n} = 0. $$ Show that $f$ ...
3
votes
1answer
94 views

Find a very slow growing function

I'm trying to find a continuous increasing function $f$ in $[1,\infty)$ such that $1-\frac{f(x)}{f(2x)} = O(1/\log^c(x))$ for some constant $c>1$, and $\lim_{x\to \infty} f(x) = \infty$. Note if ...
1
vote
2answers
26 views

Can $\Theta(f_1) = \Theta(f_2)$?

Does $\Theta(n^3+2n+1) = \Theta(n^3)$ hold? I'm so used to proving that a concrete function is Big-Whatever of another function, but never that Big-Whatever of a function is Big-Whatever of another ...
0
votes
1answer
33 views

Prove asymptotic relationship using the limit method

Prove that $$n\log(n) = o(n^{3/2})$$ using the limit method` Note that log is in base 2. I've missed a few classes due to illness and am trying to catch up. From the notes, I see that I can compute ...