# Tag Info

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


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