Code Analysis $(20$ pts$)$

Analyze the time complexity $($TC$)$ and space complexity $($SC$)$ for the WORST case for your code listed below.

Hint: be careful when analyzing string functions.

The answers must be typed, not handwritten. Handwritten answers $($on paper or on digital$)$ will have a small penalty.

Use variable names:

W $=$ number of words in paragraph

$S=$ number of words in search list

$L=$ length of largest word

$P=$ paragraph length

Even though constant maximum lengths are provided, your analysis should use the variables, P and L $,$ to show how the

program scales for longer words and paragraphs.

Copy$/$paste YOUR code in the TC document and write next to each line its time complexity. For lines that are headers of

loops, mark the TC of each small component $($e$.$g$.$ for init, condition and update for a for$-$loop$)$

Indirect insertion sort $($worst case$)-10$pts

Your code:

Your table$($s$)$:

Space Complexity: $.$

Final TC $($worst case$)=$

Binary searching in indirectly sorted data $($one word and all words$),$ worst case $-10$ pts

You code:

Your table$($s$)$

Binary search one word: SC:

Final TC $($worst case$)=.$

Binary search all words: SC:

Final TC $($worst case$)=$

Penalties:

$5$ pts penalty for answers handwritten instead of typed in the answers document $($including the tables$).$

$5$ pts penalty for not including code in this document.

$5$ pts penalty if lines of code are not annotated with their TC in this document.