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).$