Just for practice, if you find something wrong, feel free to contact me.

1. See solutions

2. We have $T(n) = n T(n-1) + 1$ and we can prove $n!\le{T(n)}\le{2n!-1}$ by induction:

• For $n=1$, it works.

• For $n\ge{2}$,

So, $T(n)=\Theta{(n!)}$

3. a). $n^3 = \omega(\lg^2n)$

b). $\lg(n^2) = 2\lg(n)$, $\lg{2^{\sqrt{2\lg{n}}}}=\sqrt{2\lg{n}}\lg{2}$, so $\lg{n^2}=\omega{(\lg{2^{\sqrt{2\lg{n}}}})}$, thus ${n^2}=\omega{({2^{\sqrt{2\lg{n}}}})}$

c). $\Theta$

d). $(3/2)^n=o(2^n)$

4. a).

b). Try Master Theorm first:
$f(n)=\frac{n}{\lg{n}}$

so $f(n)=o(n)$, $T(n)=\Theta(n)$

and

and

For $n \ge 8$, we have that $\log(x)\le2(\log(x)-1)$, thus

Combining $(1)$ though $(4)$, we get that

and we have

So

Combining $(5)$ and $(7)$ we have

5. BWTRPUZ

6. Can’t understand, Mergesort doesn’t compare indices.

7. See solutions

8. a).

a[:p] means a[0], a[1], a[2], ... , a[p-1],

a[p:] means a[p], a[p+1], ... , a[len(a)-1]

b). $T(n) = T(\frac{n}{5/3}) + n$

c).

so $f(n)=\Omega(1)$,

in order to find $0<c<1$ s.t. $f(\frac{n}{5/3})\le{cf(n)}$, $\frac{n}{5/3}\le{cn}$, just let $c=\frac{3}{5}$

so $T(n)=\Theta(f(n))=\Theta(n)$, is leaner as well.

9. a).

b). Since Vm<=V, Em<=E, as the comments on the right, we have $T=O(|V|+|E|)$

c). If a graph is semiconnected, its meta graph of SCC must be a link(only one single path), otherwise the subtrees of the branching node cannot visit each other.

10. See solutions

11. See solutions

12. We can use something like Segment Tree to do this.
a).

b). $T(n)=2T(n/2)+C$, so $T(n)=\Theta(n)$

c). If using dynamic programming, we can get another $O(n)$ algorithm, transmission formula is dp[i] = max(a[i], dp[i-1] + a[i]).