$(2$ points$)$ Given the following pseudocode:

FUNCTION DoSomething$($List$,$ LengthOfList$)$

IF LengthOfList THEN

RETURN List

END IF

SET Size TO LengthOfList $/3$

SET List$1$ TO elements from index $0$ to Size $-1$ in List

SET List$2$ TO elements from index Size to $(2*$Size$-1)$ in List

SET List$3$ TO elements from index $(2*$ Size$)$ to $(3*$ Size$-1)$ in List

SET List$4$ TO elements from index $(3*$ Size$)$ to $($Length$0$fList$-1)$ in List

res$1=$ DoSomething$($List$1,$ Size$)$

res$2=$ DoSomething$($List$2,$ Size$)$

res$3=$ DoSomething$($List$3,$ Size$)$

res$4=$ DoSomething$($List$4,$ Size$)$

combinedResult $=$ CombineResults$($res$1,$ res$2,$ res$3,$ res$4,$ Length$0$fList$)$

RETURN combinedResult

END FUNCTION

FUNCTION CombineResults$($res$1,$ res$2,$ res$3,$ res$4,$ Length$0$fList$)$

INITIALIZE Result TO $0$

FOR i FROM $0$ TO LengthOfList $-1$ DO

FOR j FROM $0$ TO LengthOfList $-1$ DO

SET Result TO Result $+i+j$

END FOR

END FOR

FOR k FROM $0$ TO LengthOfList DO

SET Result TO Result $+$k

END FOR

RETURN Result

END FUNCTION $($a$)(1$ points$)$ Analyze the provided pseudocode in detail, line by line, and derive the corre$-$

sponding recurrence relation based on your analysis.

$($b$)(1$ point$)$ Compute the Theta time complexity of this algorithm using the recurrence

relation from part $($a$)$ as a reference. Note that Back$-$Substitution is not allowed for this

problem.