Consider a Graph class that stores the graph using $an$ EdgeList data structure. When answering the following runtime questions, give the most specific runtime bound you can: $if$ a BigTheta bound exists, give that, otherwise give the tightest upper bound $(Big-O)$ you can.

$1.$ Derive the unqualified worst$-$case runtime $(in$ terms $of|V|$ and $|E|)to$

perform a $BFS$ search $on$ a Graph that $is$ implemented using $an$ EdgeList. Justify

your answer. Note:

$2.(3$ points$)To$ perform a $BFS$ search $of$ the graph, $we$ may first compute the AdjacencyList and then searched the graph. What $is$ the total unqualified worst$-$case

runtime $(in$ terms $of|V|$ and $|E|)to$ compute the AdjacencyList and then perform

the $BFS$ search.

$3.(3$ points$)$ Based on your answers to the previous questions is it worth it to take the

time to compute the AdjacencyList before performing BFS if your input Graph is

implemented using an EdgeList? Why or why not? In at most three sentences,

explain the reason.

$4.(5$ points$)$ Now imagine instead of searching a Graph of data, we are searching

an ArrayList of data. If the ArrayList contains n elements, what is the unqualified

worst$-$case runtime in terms of n to: $(1)$ Find a specific value in the ArrayList? $(2)$

Sort the ArrayList? $(3)$ Find a specific value in the sorted ArrayList? $(4)$ What is

the runtime to perform n searches in row on the original ArrayList? $(5)$ What is

the runtime to perform n searches in row on the sorted ArrayList?

$5.(3$ points$)$ Base on your answers to the previous questions, is it worth it to sort the

ArrayList first and then perform n searches? Justify your answer in at most

three sentences. Answers without justificiaton will not receive credit.

$6.(3$ points$)$ Now imagine ArrayList contains the statistics for every player in the

National Football League, and you want to find the $15$ players that have scored

the most points. Is it worth it to sort the list by points scored before doing the

search? Justify your answer in at most three sentences, answers without

justification will not receive credit.