1.
a. The number of nodes at level h is at most d^h. The total number of nodes in a tree of height h is at most 1 + d + ... + d^h = Θ(d^h). Setting d^h = n implies the height is
Θ(logd n).

b. same as binary heaps. running time is given by Heapify. Heapify operation on d-ary heaps is similar to the one on binary heaps:

Heapify_D(A, i)
i. find largest element l = max{A[i], Children(A[i])} ii. if l != i then exchange A[i] ↔ A[l] and Heapify D(A, i)

The running time of Heapify d is Θ(d · logd n). The d term is because at each iteration a node compares its value and the values of its d children to find the maximum, which takes O(d) time.
c. same as binary heaps. The running time is Θ(height) = Θ(logd n).
d. The running time is O(logd n) if A[i] < k.
Heap_Increase_Key _D(A, i, k)
i. if A[i] < k then
A[i] = k while i > 1 and A[Parent(i)] < A[i] do exchange A[i] ↔ A[Parent(i)] i = Parent(i)

2. log(n!) = log(1) + log(2) + ... + log(n-1) + log(n) log(1) + log(2) + ... + log(n) <= log(n) + log(n) + ... + log(n) = n*log(n) log(1) + ... + log(n/2) + ... + log(n) >= log(n/2) + ... + log(n)>= log(n/2) + ... + log(n/2) = n/2 * log(n/2)
3.
T(n) is the best-case time for the procedure QUICKSORT on an input of size of n.
T(n) = min (T(q) + T(n − q − 1)) + Θ(n))
1≤q≤n−1
We guess that T(n) ≥ cn lg n
->
T(n) ≥ min (cq lg q + c(n − q − 1) lg(n − q − 1)) + Θ(n) (1≤q≤n−1)
= c min(q lg q + (n − q − 1) lg(n − q − 1) + Θ(n) (1≤q≤n−1)

Choosing q = (n − 1)/2 gives us the bound min(q lg q + (n − q − 1) lg(n − q − 1) >=(n-1)/2*lg[(n-1)/2]+[(n-(n-1)/2-1)]lg(n-(n-1)/2-1)=(n-1)lg[(n-1)/2]
Continuing with our bounding of T(n), we obtain, for n ≥ 2,
T(n) ≥ c(n − 1) lg [(n – 1)\2]+ Θ(n)
= c(n − 1) lg(n − 1) − c(n − 1) + Θ(n)
= cn lg(n − 1) − c lg(n − 1) − c(n − 1) + Θ(n)
≥ cn lg(n/2) − c lg(n − 1) − c(n − 1) + Θ(n) since n ≥ 2
= cn lg n − cn − c lg(n − 1) − cn + c + Θ(n)
= cn lg n − (2cn + c lg(n − 1) − c) + Θ(n)
≥ cn lg n
->故得證