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
2answers
61 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
vote
0answers
28 views

Asymptotic behaviour of $\varphi''(x)=F(\varphi(x))$

I'm concerned with the discussion of a ODE, especially the discussion of the solution. I've got the assumptions that there is the relation $\varphi''(x)=F(\varphi(x))$ for all $x$ on $\mathbb{R}$. ...
0
votes
1answer
34 views

Proving $\lg n!=\Omega(n\lg n)$

In the answer given in the book for the proof of $\lg n=\Omega(n\lg n)$ there are several steps which I don't understand . $$\lg n!=\lg n+\lg(n-1)+\lg(n-2)+ ....+\lg(2)+\lg 1$$ Then it says that ...
0
votes
1answer
34 views

Binomial coefficients and order of infinity

Which among $$ \left(2\,k+1 \atop j\right),~~j=1,3,5,...,2\,k+1 $$ has the larger order of infinity when $k\rightarrow\infty$? I am pretty sure that the largest order is reached around $j=k$ but I ...
1
vote
1answer
251 views

Proving functions to be Big Oh

How do I determine if there exists a function $f$, such that \begin{equation} f(n) = {\mathcal O}(\log n), \end{equation} but \begin{equation} 2^{f(n)} ≠ {\mathcal O}(n). \end{equation} Is ...
1
vote
1answer
32 views

Question about Growth Rates

I see in some notes from my instructor in Algorithm course that $\Sigma_{i=0}^{log n} (n/2^i)$ has growth bigger than $\Sigma_{i=1}^{n} (i log i)$. i couldn't understand why? any tutorial or hint?
0
votes
0answers
67 views

How do I prove that $f(n) + O(f(n)) = \Theta(f(n))$?

Here's what I have so far: $f(n) = \Theta(f(n))$ $C_1 f(n) < f(n) < C_2 f(n)$ $C_1f(n) + O(f(n)) < f(n) + O(f(n)) < C_2f(n) + O(f(n)) $ And then I run out of gas. The equal to sign ...
1
vote
2answers
28 views

Big O notation - proof

Is it true that $O(k(n) + m(n))$ is equal to $O(\max\{k(n), m(n)\})$? In one of papers on computational complexity I've found the following statement: $$O(\log(n) + n(\log S + \log V )) = O(n(\log ...
0
votes
1answer
66 views

Prime number theorem lemma: prove that $\psi(x)\sim\pi(x)\log(x)$

I'm trying to follow the proof in Wikipedia that the PNT is equivalent to the assertion $\psi(x)\sim x$, by proving that $\psi(x)\sim\pi(x)\log x$, which it claims is a very simple proof. One ...
0
votes
0answers
15 views

Algorithm that adds three numbers in an array that performs in O(n^2) time

Note that this question extends on this previous question. Given an array A, and a value called value. Does there exist three ...
0
votes
2answers
16 views

Designing a fast algorithm which adds three numbers in array

Given an array A, and a value called value. Does there exist three elements in A where their ...
2
votes
1answer
52 views

What is the bound on $E\|Y_n\|^4$ in terms of $n$?

Let $X_n,n\in\mathbb{N}$ be i.i.d. zero-mean random variables in some separable Hilbert space with $E\|X_n\|^8<\infty$ and $Y_n=\frac{1}{n}\sum_{i=1}^nX_n$. I need to find bounds on $E\|Y_n\|^4$. ...
1
vote
2answers
26 views

Help analyzing the time-complexity of my algorithm

So, (this is homework), we are given an array A, and we are asked to create a function where we return True/False if the array contains three elements which sum to a given value. To formalize: ...
1
vote
1answer
22 views

Series expansions and perturbation

My professor said that $ f \left( y_1(x)+ \epsilon y_2(x)+... \right)= f(y_1(x)) +f'(y_1(x))\> (\epsilon y_2(x)+...) + ...$ but I have no idea how the series continues. Has anyone seen this ...
0
votes
1answer
45 views

Big-Oh of exponent of exponent

How does one whether an exponent of an exponent is the big-Oh of the other? For example, if I have $a^{b^n}$ and $b^{a^n}$, how would i determine and prove which is a big oh of another? I'm thinking ...
7
votes
0answers
138 views

Is it true that $\gamma_{\lfloor\log\Gamma(x)\rfloor}\sim 2\pi x$?

I realise that Gram points can approximate the imaginary part on the $x$th zeta zero $(\gamma_x)$ accurately, and indeed, Guilherme França, André LeClair give another formula, namely ...
1
vote
1answer
378 views

Solving the recurrence $T (n) = \sqrt{n} T(\sqrt{n}) + O (n)$ [duplicate]

I want to show that the requrrence $T (n) = \sqrt{n} T(\sqrt{n}) + O (n)$ is in $O(n \log \log n)$ Here's my attempt: If we expand the recursion tree, at a level $i$, there are $n^{1/2^k}$ ...
1
vote
1answer
40 views

An inverse problem on tail probability

This is a question out of curiosity. Assume that $f(x)$ is a density function for which there is a constant $C>0$ so that $$ \int_t^\infty f(x) dx \le C f(t) $$ holds for large enough $t>0$. My ...
2
votes
1answer
50 views

Using Big-O to analyze an algorithm's effectiveness

I am in three Computer Science/Math classes that are all dealing with algorithms, Big-O, that jazz. After listening, taking notes, and doing some of my own online searching, I'm pretty damn sure I ...
3
votes
2answers
23 views

is there a pair of functions that meets the next requirement?

How i can find a pair of functions that meets the next requirement $f,g: \mathbb{N} \rightarrow \mathbb{R^+_0}$ And that $f(n) \not \in O(g(n))$ and $g(n) \not \in O(f(n))$ also these functions must ...
0
votes
1answer
54 views

How to prove the $\Theta$ notation?

I know that to prove that f(n) = $\Theta$(g(n)) we have to find c1, c2 > 0 and n0 such that $$0 \le c_1 g(n) \le f(n) \le c_2 g(n)$$ I'm quite new with the proofs in general. Let assume that we ...
0
votes
2answers
26 views

Proving Algorithms

I'm trying to get down how to prove that something is $O(\cdots)$ or $\Theta(\cdots)$ but no matter what I look at, I don't get the reasoning as to how I can come to an answer. So here's a couple of ...
0
votes
2answers
51 views

Show that $f(x) = x^2 + 5x + 9$ is $O(x^2)$.

Show that $f(x) = x^2 + 5x + 9$ is $O(x^2)$. This involved the big O notation. I can understand a bit of big O notation but answering this question to me is difficult. None of the examples I have ...
1
vote
2answers
43 views

Proving that: 800 + n log n + 200√ n log n = Θ(n log n)

I am trying to prove that 800 + n log n + 600sqrt(n)*log(n) = Θ(n*log n) (where log is base 2) Basically so far, I've reduced this expression into an ...
0
votes
1answer
26 views

Comparing the order of convergence $\mathcal{O}( h^2 |\log(h)|)$

I don't have any intuition in judging how fast a term of the order $\mathcal{O}( h^2 |\log(h)|)$ is decreasing as $h \to 0$, so i tried comparing it with terms of the form $\mathcal{O}( h^\alpha )$ ...
1
vote
1answer
36 views

Does $f(2x) \in Θ(f(x))$ always hold?

If $f(x)$ is continuous and increasing positively, does $f(2x) \in Θ(f(x))$? I am convinced that this is false but I am stuck on the proof. $$0 \le c_1 f(x) \le f(2x) \le c_2 f(x)$$ $$0 \le c_1 \le ...
1
vote
2answers
40 views

If f(n) = O(n), does log(f(n)) = O(log n)?

I have been trying to find a counter-example to prove this is false, however I feel that I am going in the wrong direction. f(n) = O(n), does lg(f(n)) = O(lg n) ...
1
vote
2answers
36 views

Partitions tending to a constant

$P_{k}(n)$ = the number of partitions of n into k parts. Now, if we fix some $t\ge 0$ , then $\lim_{n\to\infty}P_{n-t}(n)\to$ c, c being some constant. Please help me with this! I believe ...
-1
votes
1answer
37 views

Prove $\left\lfloor n\right\rfloor = n + O(1)$

Can someone show me why $\left\lfloor n\right\rfloor = n + O(1)$. Using the same logic, can anyone derive a similar proposition for $\left\lceil n\right\rceil$?
7
votes
2answers
111 views

Why is this function a really good asymptotic for $\exp(x)\sqrt{x}$

$$f(x)=\sum_{n=0}^{\infty} a_n x^n\;\;\;\;\; a_n = \frac{1}{\Gamma(n+0.5)}$$ Why is this entire function a really good asymptotic for $\exp(x)\sqrt{x}$, where for large positive numbers, ...
0
votes
1answer
25 views

What is a polynomially bounded function?

I know this question has been answered before, but I didn't understand the answers and my reputation is too low to comment, since I'm new to stack exchange. Polynomially bounded (I'm pretty sure) ...
3
votes
3answers
277 views

Find a real entire function $f(z)$ asymptotic to $\ln(x^2+1)$ for real $x$.

Find a real entire function $f(z)$ asymptotic to $\ln(x^2 +1)$ for real $x$. More specific I want $f(0)=0$ and $\frac{1}{2} \ln(x^2+1) < f(x) < 2 \ln(x^2+1)$. Or prove it does not exist.
0
votes
1answer
23 views

How to extract $O(h^2)$ from $f\left(t_{i+1},y_i+hf(t_i,y_i)+O(h^2)\right)$

This is the formula of explicit Heun's method $$ y_{i+1}=y_i+hf\left(t_{i+1},y_i+hf(t_i,y_i)+O(h^2)\right)+O(h^3) $$ and I want to prove that this formula is $O(h^3)$.
9
votes
2answers
6k views

Quicksort Running Time

I am trying to refresh my knowledge (and hopefully learn more) about Algorithm Analysis. I took a course on this two years ago but I am trying to catch up on what I had learned back then. The way I ...
0
votes
0answers
26 views

Question about computing two asymptotics

Fix $k$. Is there a constant $c \in (0,1)$ such that if $L=cn$ and $n$ tends to infinity then $$\frac{(2k)!}{2^kk!}{2nL - L^2 \choose 2k} \sim \sum_{s=0}^k{L \choose s}{n-L \choose ...
0
votes
2answers
36 views

Order of error of a fraction

If two functions can be written as the sum of some expression and an error term of higher orders of error $\epsilon$: $$f(x+\epsilon)=f_0(x,\epsilon)+O(\epsilon^m)\quad \text{ and} \quad ...
0
votes
0answers
13 views

Asymptotics of two expressions

I'd like to know something about this equation $\frac{(2k)!}{2^kk!}{2nL - L^2 \choose 2k} = \sum_{s=0}^k{L \choose s}{n-L \choose s}s!\frac{(2k-2s)!}{2^{k-s}(k-s)!)}{L-s \choose 2k-2s}.$ I am ...
0
votes
0answers
42 views

What's the right way to write big-O?

I always write $\mathcal{O}(n)$ (\mathcal{O}(n)). But I frequently see $O(n)$ (O(n)), probably because it's shorter and more ...
1
vote
0answers
54 views

sum over primes involving divisor function (variation of the Titchmarsh divisor problem)

Does there exist an asymptotic estimate for the following sum over primes $$ \sum_{p\leq x} \frac{\tau(p-1)}{p}\;, $$ where $\tau(n)=\sum_{d|n}1$ is the divisor function?
1
vote
1answer
35 views

What is the result of $\frac{h^2}{2}O(h)+O(h^3)$

Why and how in the following expression $$ y_{n+1}=y_n+hy^{\prime}_n+\frac{1}{2}\left[ \frac{y^{\prime}_{n+1}-y^{\prime}_n}{h}+O(h) \right]h^2+O(h^3) $$ $$\Rightarrow y_{n+1}=y_n+h\left( ...
0
votes
1answer
24 views

What are basic methodologies on solving questions related to comparison of rate of growth of two different functions?

How to compare rate of growth for following functions? In other words, is $f(n)$ = $O( \, g(n) \, )$ or $g(n)$ = $O(\, f(n) \, )$? $f(n) = n^{\frac{4}{3}}$ and $g(n) = n*(\log(n))^3$ How to solve ...
0
votes
1answer
92 views

Asymptotic distribution of MLE of geometric distribution

I need to find the asymptotic distribution of the MLE of a geometric distribution. I know $\overline X$ goes as $N(1/p, (1-p)/(n p^2))$. Using the delta method MLE=$1/\overline X$ goes as $N(p, ...
1
vote
2answers
37 views

O-notation: composing functions

Big-oh and little-oh notation make things much simpler, and there are convenient rules for combining functions, for example, the ones mentioned here. One rule conspicuously missing from the above ...
1
vote
2answers
50 views

Series expansion of incomplete gamma function ratio

I am interested in the series expansion of: $$S(k)=\frac{\Gamma(k+1,a)}{k!},$$ around $k=\infty$ where $\Gamma(x,z)$ is the incomplete gamma function and $a$ is some positive constant. In ...
1
vote
3answers
67 views

Is $(n^{1/n}-1)\in O(n^{-\frac12})$ as $n\to \infty$?

Let $$x_n=n^{1/n}-1$$ An exercise asks me to prove that $\{x_n\}\to 0$ and that $x_n\in O(n^{-\frac12})$ as $n\to \infty$. Now, I could easily prove the first part. But to me $x_n\notin ...
2
votes
0answers
27 views

Comparing asymptotic growth of logarithmic functions by reasoning

As an exercise, we're sorting functions according to their asymptotical growth. When comparing these two functions, I'm getting stuck: $n^2/(\log_2 n)^3$ versus $n \log_2 n$. Using limits I am ...
0
votes
1answer
19 views

Finding family of curve for given asymptotes

I need to find possible curves, with asymptotes given as $x=0 (x \to -\infty)$ and $y=mx \hspace{0.5cm} m>0$. it is easy to find curves for individual lines, $y= \exp(-\lambda_1 x) + mx$ for $y=mx$ ...
1
vote
1answer
28 views

How can I construct a specific sigmoid function?

The simple sigmoid function $$f(x)=1/(1+e^{−x})$$ approaches zero as x tends to negative infinity, and approaches $1$ as x tends to positive infinity. But I want to set $1$ and $20$ instead of $0$ and ...
1
vote
2answers
31 views

How can I find The Big Oh bounds for a summation with multiple variables?

I have this as a homework problem so I won't post the same thing. I'll just post what I need to know to move forward. $$ \sum_{i=0}^n 10^i i^2 $$ I'd just like to know how to split this ...
7
votes
2answers
3k views

Value of Summation of $\log(n)$

Context: I am learning Dijstra's Algorithm to find shortest path to any node, given the start node. Here, we can use Fibonnacci Heap as Priority Queue. Following is few lines of algorithm: ...