$1$ Problem $4[15$ pts$]$

Problem $4.$ Analyze the worst$-$case runtime of the following algorithm:

$1.$ Clearly derive the runtime complexity function T $($n$)$ for this algorithm.

$2.$ Using the formal definition of Big$-$Theta $(\backslash$Theta $),$ find a tight asymptotic bound for T $($n$),$ that is$,$ find a

function f $($n$)$ such that T $($n$)=\backslash$Theta $($f $($n$)).$

Avoid heuristic arguments from CSCI $2270/2824$ such as multiplying the complexities of nested loops.

Algorithm $1$ Nested Algorithm $1$

$1$: procedure IndependentNested$1($Integer n$)$

$2$: for i $1$; i $<=$ n; i $$ i $2$ do

$3$: for j $1$; j $<=$ n; j $$ j $+2$ do