a$)$ Give the worst case complexity of the following code fragment in the Big $$ notation. The algorithm's input is an array of characters $A$ of size $n.$ What does the algorithm compute?$[5$ marks$]$b$)$ For each of the following pairs of functions, state which one grows faster asymptotically for input of size n$,$ in other words, is worse in terms of efficiency.i$.$ quad f$($n$)=$nlog$\_(2)$n$+53$ and k$($n$)=10$log$\_(2)$n$+53[2$ marks$]$ii$.$ quad f$($n$)=$n$^($n$)$ and k$($n$)=$n$^(5)+$n$^(4)+68[2$ marks$]$iii$.$ quad f$($n$)=2^($n$)$ and k$($n$)=$n$^(2)+100$ n$+2[2$ marks$]$iv$.$ quad f$($n$)=$ square$-$root $($n$)$ and k$($n$)=$n$^(2)+$log$\_(2)($n$)$d$)$ Imagine an algorithm that searches for an integer in an array of integers by first using insertion$-$sort to sort the array and then using binary$-$search to search for the number. State the best case and worst case complexities of this algorithm in the Big Theta notation.$[4$ marks$][$Total $25$ Marks$]$c$)$ For each problem listed in the left$-$most column of the table and for each of the properties listed in the other columns, do the following:

Put $T$ if the property is true for the problem and put $F$ if the property is false. Be careful to reproduce this table clearly in your answer book.

$\backslash$table$[[$Problem$,$Is Decision Problem,Is Tractable,Is in NP$,\backslash$table$[[$Is in NP$-],[$Complete$]]],[\backslash$table$[[$Shortest road$],[$between any two$],[$cities in England$]],,,,],[\backslash$table$[[$Is given number in$],[$the array$]],,,,],[\backslash$table$[[$Sorting array of$],[$integers$]],,,,],[\backslash$table$[[$Propositional$],[$satisfiability$]],,,,]]$