3

By definition, $f(n) \leq c_1 \cdot g(n)$ and $l(n) \leq c_2 \cdot m(n)$, for some $c_1$ and $n \geq n_0$, and for some $c_2$ and $n \geq n_0'$ respectively. Suppose we set $n_0^* = \max (n_0, n_0')$, then both inequalities are satisfied for $n \geq n_0^*$. Then obviously $f(n) \cdot l(n) \leq c_1 \cdot g(n) \cdot c_2 \cdot m(n)$ for $n \geq n_0^*$. So ...


3

Suppose for simplicity that $m=2^a$, $n = 2^b$, $c_0=1$, $c_1=0$, and the base cases are $T(1,\cdot) = T(\cdot,1) = 0$. Then $$ T(2^a,2^b) = 2T(2^{a-1},2^{b-1}) + b = 4T(2^{a-2},2^{b-2}) + b + 2(b-1) = \cdots $$ The number of summands is $c = \min(a,b)$, and using this notation we obtain \begin{align} T(2^a,2^b) &= b + 2(b-1) + 4(b-2) + \cdots + 2^{c-1}(...


3

Part 1 I'm going to do something I decided I wouldn't do: try to nutshell my research on this topic. I'll go over on how the algorithmic O-notation must be defined, why it is probably not what you've been taught, and what other misconceptions float around this topic. I wrote this in the form of an imaginary discussion. The following discussion is based on ...


2

Part 2 $$ \newcommand{\TR}{\mathbb{R}} \newcommand{\TN}{\mathbb{N}} \newcommand{\subsets}[1]{\mathcal{P}(#1)} \newcommand{\setb}[1]{\left\{#1\right\}} \newcommand{\land}{\text{ and }} $$ Algorithms Are there cases where existing intuition on O-notation may not hold? You may find that your existing intuition does not hold when the input-set is something ...


2

You still need to shift $O(n)$ elements to make room for the newly inserted element even if you find the correct position in $O(\log n)$.


2

Let us replace $\Theta(n)$ with $n$, for concreteness, and assume a base case of $T(0) = 0$. Let's try to prove inductively that $T(n) \geq cf(n)$, where $f(n) = n\log n$ for all $n$ (where $0\log 0 = 0$). During the proof, we will need to minimize $f(q) + f(m-q)$ for $0 \leq q \leq m$. Since $f'(n) = \log n + 1$, any minimum point must satisfy $$ \log q + ...


2

You can write your recurrence as $$ T(n) = \sum_{i=1}^k a_i T(b_i x + h_i(n)) + g(n) $$ with: $k=2$ $a_1 = a_2 = 1$ $b_1 = \frac{1}{2}$, and $b_2 = \frac{1}{3}$ $h_1(n) = h_2(n) = 0$ $g(n) = 1$ From Akra–Bazzi theorem, the solution to your recurrence is $T(n) = \Theta\Big( n^p \big(1 + f(n)\big)\Big)$, where $p$ is such that $a_1 b_1^p + a_2 b_2^p =1$ and ...


2

The mistake and correction $$T(n)= 2T(n/2) + \theta(n^2)$$ As you intended, $T(n)$ is the worst time of mergesorting $n$ strings of length $n$. Then, $T(n/2)$ on the RHS means the worst time of mergesorting $n/2$ strings of length $n/2$. So during the mergesort, the length of strings shrinks from $n$ to $n/2$! What should have been done is using a ...


1

First of all, if $k$ and $n$ are bounded then all complexities trivialize to $O(1)$. Hence a better assumption is something like $k = O(\log n)$. Under this assumption, you can, for example, say that $O(k + n) = O(n)$, and even $O(k + \log n) = O(\log n)$. However, you cannot say that $O(kn) = O(n)$, since it's not necessarily true! If $k = \log n$, then it'...


1

What I recommend first is to notice that if you're looking at the complexity of the function $3x^2+2x+1$, really all you should care about is the function $x^2$. because if you will prove that $x^2 = \omega(xlogx)$ then adding the $2x + 1$ won't ruin that proof since $x^2$ is polynomially bigger than $2x + 1$ and so we can just look at the $x^2$. (I will ...


1

The easiest way is to check that $\lim_{x \to \infty} \frac{3x^3 + 2x +1}{ x \log x} = +\infty$, which is a sufficient condition for $3x^3 + 2x +1 \in \omega(x \log x)$. $$ \lim_{x \to \infty} \frac{3x^3 + 2x +1}{ x \log x} = \lim_{x \to \infty} \frac{3x^3}{ x \log x} = \lim_{x \to \infty} \frac{3x^2}{ \log x} = \lim_{x \to \infty} 6x^2 = +\infty. $$


1

Your formulation of $f(n) \neq o(g(n))$ is wrong. Recall that $f(n) = o(g(n))$ if for all $c > 0$ there exists $n_0$ such that for all $n \geq n_0$, we have $f(n) \leq cg(n)$. The negation of this is: there exists $c > 0$ such that for all $n_0$ there exists $n \geq n_0$ such that $f(n) > cg(n)$. Take $c = 1$. Given $n_0$, let $n = \max(n_0,10^{...


1

One possibility is to merely apply the definition. That is, we see that if $\lim_{n \to \infty} f(n) / g(n) = 0$, then $f(n) = o(g(n))$. Computing this, we have that $$\lim_{n \to \infty} f(n) / g(n) = \lim_{n \to \infty} n^n/10^{10n} = \infty \neq 0.$$ We conclude that $f(n) = o(g(n))$ does not hold.


1

You can use the recursion tree method. The amount of work on the level at depth $0$ is at least $c n$ for some constant $c$ (from the $\Theta(\cdot)$ notation). The amount of work at depth $1$ is at least $c q + c (n-q -1) = c(n-1)$. The amount of work on the next level is at least $c(n-3)$ and, in general, the total amount of work on the level at depth $d$ ...


1

It is possible. Example $g_A(n)=1$, $g_B(n)=2$, and $f(n)=1$. It is also necessary, since $g_B(n) = 2 g_A(n) \in\Omega(f(n))$. To see that $ 2 g_A(n) \in\Omega(f(n))$ you can use the definition of $\Omega(\cdot)$. From $g_A(n) = \Omega(f(n))$ you know that here is some $n_0$ and some $c>0$ such that, $\forall n \ge n_0$, $g_A(n) \ge c f(n)$. This ...


1

If you express the runtime relative to the input value, it is O(f(n)). But often we describe the runtime relative to the input size; for k bit input it is $O(f(2^k-1))$. Now I guess the m-th ugly number is greater than $2^{m^{1/3}}$, so this grows quite quickly. It would grow so fast that divisibility by 2,3 and 5 only cannot be checked in constant time. ...


Only top voted, non community-wiki answers of a minimum length are eligible