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

learn more… | top users | synonyms (1)

0
votes
1answer
18 views

use substitution method to prove an equation is in O(n log2 n)

I am trying to prove that the equation: T(n) = 2T((n/2) +17) + n is O(n log_2(n)) I have to do this by using substitution ...
1
vote
1answer
11 views

Big-O proof, and the relationship between two different Big-O functions

One question on my homework is as follows: Let $f_1, f_2, f_3, f_4$ be functions from the set $N$ of natural numbers to the set $R$ of real numbers. Suppose that $f_1= O(f_2)$ and $f_3=O(f_4)$. Use ...
0
votes
0answers
11 views

Asymptotic parameter for a transcendental equation

I need to find the roots of the following equation $(x^2-a^2)(x^2+a^2)\sin(b^2-x^2)-b^2 \cos(\sqrt{b^2-x^2})=0$. Say $\mathcal{A}=(x^2-a^2)(x^2+a^2)$. I assume that as long as $x$ is away from its ...
0
votes
0answers
12 views

Is this operation valid when doing time-complexity analysis?

I am analyzing the time-complexity of an algorithm that uses binary-search to solve the 3SUM problem. I am asked to give the big-oh and big-theta timings. \begin{align*} \sum_{i=1}^n \sum_{j=1}^i ...
0
votes
2answers
41 views

Limiting cases for $a/(b+a)$

Maybe a simple question but I am a bit stuck with it. $\frac{a}{b+a}$ is a part of the equation that I have to solve in two limiting cases. For $b\ll a$ we can skip $b$ and it ends up in ...
1
vote
1answer
27 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
29 views

Need help with an algorithmic function [on hold]

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
37 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
21 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
24 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
12 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
24 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
1answer
25 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
29 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 ...
4
votes
1answer
21 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
42 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
12 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
64 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
15 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
21 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
16 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
46 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
35 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
votes
0answers
18 views

basic question of the asymptotics algebra [closed]

I am trying to teach myself algorithms, I am following along an online web course, I need help with following questions 1) Prove that if $f(n) = O(g(n))$ and $f(n) = W(g(n))$, then $f(n) = Q(g(n))$. ...
1
vote
1answer
36 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
21 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
22 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
46 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
47 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
35 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
47 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
23 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
34 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
36 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
33 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
20 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
98 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
30 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
31 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
35 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
39 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
22 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
32 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
11 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 ...