Qu $1$: The following algorithms are for the operations of a Singly Linked List, $L.$ It is assumed that the list has $2$ attributes, head and tail referencing the first and last node respectively. Each node of the list is assumed to have $2$ attributes. info. and next referencing the data item in the node and the next node respectively.

$h$

il

For each of the algorithms, use the provided table to perform a line$-$by$-$line analysis and then answer each of the following questions:

$($i$)$ Find the general running time function, $T(n),$ where $n$ is the number of elements in the list.

$($ii$)$ Explain the worst case scenario $($or explain why there is no best$/$worst case scenario$)$

$($iii$)$Find the worst$-$case running time. If there is no worst case, find the running time for any of the possible scenarios.

$($iv$)$ Write the running time you find in $($iii$)$ above using $$ notation.

You may assume that the running time of all basic operations is constant.

$]=[5$ Marks

$\backslash$table$[[$a$),\frac{\frac{?}{?}}{?}$ Adds a node containing the data value, $el,$ at the end of$,$list, $L,$sumes the list is not empty.$],[,$List$\_$Add$\_$To$\_$Tail$($L$,$ el$),$Cost,Times$],[,$if $\frac{?}{\text{b}\text{a}\text{r}}(L).\frac{i}{b}ar(s)Empty(),,],[,$L$.$head $=$ new Node $(el),,],[,$L$.$tail $=$ L$.$head,,$],[,$else,,$],[,$L$.$tail.next $=$ new Node$($el$),,],[,$L$.$tail $=$ L$.$tail.next,,$]]$

$\backslash$table$[[$b$),//$Deletes and returns the last element in the list, $L.$ It assumes the list contains more than one element$],[,$List Delete From Tail$($L$),$Cost,Times$],[,1,el=L.$ tail.info,,$],[,x=L*$ head,,$],[,$while x$.$next $!=$ tail,,$],[,x=x.$ next,,$],[,$L$.$tail $=x,,],[,$L$.$tail.next $=$ NIL,,$],[,$return el$,,]]$

Page $2$ of $2$

$\backslash$table$[[$c$),//$Finds and returns the first element less than the given targe,Returns :$,f$ is not found$],[,\backslash$table$[[Lis{t}_{F}in{d}_{L}es{s}_T$han$(L,$target$)$