Midterm Answer Structure

Solution

Do the operations depend on the input?

This is not a direct dependency, but rather are there different cases which happen or is it a worst case scenario every time.

Describe what the input for the worst case

Note roughly what branches would follow to produce the worst case

Split the algorithm into parts

Denote each part as $T_x(N)$ where $x$ is $a,b,c,...$

Describe if the algorithm’s composition

Typically each is sequentially composed if it is not recursive.

If it is sequentially composed $T(N)$ can be described as: $T(N)=T_a(N)+T_b(N)+...$ If it is not sequentially composed: $T(N)=T_a(N)\ast T_b(N)...$ Decide if you should use $O(N)$ or $\Theta (N)$.

$\Theta (N)$ seems to be used in all non recursive examples, but $O(N)$ in recursive examples. Note: See Notations.

Run Time Cost

Analyse each section

Look at the time complexity of each one individually and mention why each is constant time or otherwise.

Summary

When adding $T(N)$, simply take the most complex run time and discard the rest.

Memory Cost

Brevity

While in theory both run time and memory sections should be around the same length, in practice memory sections seem to be far shorter than run time sections.

Analyse each section

Look at the memory complexity of each one individually and mention why each is constant memory or otherwise.

Summary

When adding $T(N)$, simply take the most complex memory usage and discard the rest.