Q$6$: $($True$/$False with justification$)$

We can determine how good an algorithm by it is

conditions of correctness, time efficiency and space

efficiency.

For the following pseudocode of Insertion Sort the Basic

operation of the code is for loop.

InsertionSort$(A,n)\{$

for $i=2ton\{$

key$=A[i]$

$j=i-1$;

while $(j>0)$ and $(A[j]>$key$)\{$

$A[j+1]=A[j]$

$j=j-1\}$

$A[j+1]=$key,$\},\}$

The time needs for basic operations in the previous

algorithm is $O(n^3)?$

Let $T(n)$ be a function obeying the recurrence $T(n)=$

$2T(\frac{n}{2})+$a with initial condition $T(1)=b,$ where a and

$b$ are positive numbers. Then $T(n)=(nlogn).$

Q $7$: Consider the following algorithm

ALGORITHM Mystery $($n$)$

Slarr$0$

for ilarr$1tondo$

$SBS+i**i$

Return $S$

$($a$)$ What does the algorithm computes?

$($b$)$ Write the running time for each line, and

derive the exact time?

$($c$)$ What is the basic operation?

$($d$)$ What is the efficiency class of this

algorithm?

$($e$)$ Can we do better algorithm?

Q$8$: Solve this Recurrence equation using $n=2^k$

$T(n)=\{\begin{array}{cc}c,& n=1\\ 4T(\frac{n}{2})+nlogn,& n>1\end{array}$