Tagged Questions

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
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
65 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
48 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
101 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
67 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
61 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
53 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
28 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
53 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
18 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
27 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
88 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
24 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
26 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 ...
0
votes
1answer
30 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
17 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
25 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
15 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 ...
-1
votes
2answers
56 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
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
33 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
26 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
59 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
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
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
43 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
39 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
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 ...
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 ...