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
33 views

Show $\frac{n}{2} \log(n!) = \Omega (n^2 \log(n))$

I am trying to show that $\frac{n}{2} \log(n!) = \Omega (n^2 \log(n))$ but I seem to get a conflicting result. What i did is: $n!=1*2*3*...*n \leq n*n*n*...*n=n^n$, so $\frac{n}{2} \log(n!) \leq ...
-1
votes
1answer
36 views

Need help with an algorithmic function [closed]

Consider the following claim: for any positive constant c, f(cn) ∈ Θ(f(n))? Either show the claim is true or give a counterexample.
0
votes
2answers
45 views

Need help ordering a list of functions

List the functions below from lowest order to highest order. If any two or more are of the same order, indicate which. $n$, $n^3$, $2^n$, $\ln n$, $n^2$, $\ln^2 n$, $\sqrt n$, $2^{n−1}$, $\ln n$, ...
0
votes
1answer
24 views

Show that $n^a$ is in $O(n^b)$ but $n^b$ is not in $O(n^a)$, where $0 < a < b$.

Let $a$ and $b$ be real numbers such that $0 < a < b$. Show that $n^a$ is in $O(n^b)$ but $n^b$ is not in $O(n^a)$.
1
vote
0answers
27 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
0answers
13 views

Is my proof correct : $\sum\limits_{i=0}^b a_in^i = \Theta(n^b)$

I want to prove : $$\sum\limits_{i=0}^b a_in^i= \Theta(n^b), a_o,a_1,...,a_b\in R, a_b \ne 0$$ So first, I prove that $\sum\limits_{i=0}^b a_in^i= O(n^b)$. First, Let's find $c$ $$ 0\le a_o + a_1n + ...
0
votes
1answer
32 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 ...
1
vote
2answers
29 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 ...
0
votes
1answer
31 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 ...
5
votes
1answer
27 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?
1
vote
2answers
25 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 ...
1
vote
2answers
57 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 ...
0
votes
1answer
63 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
0answers
65 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 ...
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 ...
1
vote
2answers
25 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
21 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 ...
2
votes
1answer
49 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$. ...
0
votes
1answer
42 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 ...
1
vote
1answer
38 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 ...
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
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
1answer
51 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
50 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
40 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 ...
2
votes
1answer
49 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 ...
0
votes
1answer
25 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
votes
1answer
34 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$?
0
votes
1answer
22 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) ...
7
votes
2answers
107 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, ...
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 ...
0
votes
1answer
22 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)$.
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
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
2answers
32 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
37 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
43 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
34 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 ...
1
vote
2answers
33 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 ...
2
votes
0answers
17 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 ...
1
vote
2answers
41 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 ...
0
votes
1answer
14 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
24 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
28 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 ...
0
votes
1answer
32 views

What is $\ O\left({n\over \left(\log \log n\right)^2}\right) $ equal or approximately equal to?

I already know big O notation and its use, but I can understand neither its value (or its approximation) in a "normal, ordinary" form (I'm referring to stuff like $\ n^2, 2n+1, 2^n $ etc.), nor ...
1
vote
0answers
39 views

Using Limits to Determine Big-O, Big-Omega, and Big-Theta

I am trying to get a concrete answer on using limits to determine if two functions, $f(n)$ and $g(n)$, are Big-$O$, Big-$\Omega$, or Big-$\Theta$. I have looked at my book, my lecture notes, and have ...