$3.$ Let Q be an implementation of a min priority queue where:

$-$ Q$.$Init$()$ takes $\backslash$Theta $(1)$ time. Initially, Q has $0$ elements.

$-$ Q$.$Insert$($x$)$ takes $\backslash$Theta $($log$($s$))$ time where s is the number of elements in Q$.$ Q$.$Insert$()$ adds one element to Q$.$

$-$ Q$.$DeleteMin$()$ takes $\backslash$Theta $($s$)$ time where s is the number of elements in Q$.$

Q$.$DeleteMin$()$ removes one element from Q$.$

Consider the following procedure whose input is an undirected graph G$.$ Edges G$.$E are represented by an adjacency LIST.

weight$($vi$,$ vj$)$ is a positive weight assigned to edge $($vi$,$ vj$).$

weight$($vi$)$ is a positive weight assigned to vertex $($vi$).$

$```$

Proc$3($G$)$

$1$ Q$.$Init$()$;

$2$ foreach vertex vi of G$.$V do

$3$ foreach edge $($vi$,$ vj$)$ incident on vi do

$4$ Q$.$Insert$($weight$($vi$)*$ weight$($vi$,$ vj$))$;

$5$ end

$6$ end

$7$ y ;

$8$ for each vertex vi of G$.$V do

$9$ if $($Q$.$Size$()!=0)$ then

$10$ y y $+$ Q$.$DeleteMin$()$;

$11$ end

$12$ end

$13$ return $($y$)$;

$```$

Let n be the number of vertices of G and let m be the number of edges of G$.$

For this problem, assume that m $>=$ n$.$

$($a$)$ Analyze lines $1-6$ of Proc$3$ giving a bound on their asymptotic running time in terms of n and m$.$

$($b$)$ Analyze lines $7-13$ of Proc$3$ giving a bound on their asymptotic running time in terms of n and m$.$

$($Note: Assume that m $>=$ n$.)$

$($c$)$ Give the asymptotic running time of Proc$3$ in terms of n and m$.$Let $Q$ be an implementation of a min priority queue where:

Q$.$Init$()$ takes $(1)$ time. Initially, Q has $0$ elements.

Q$.$Insert $(x)$ takes $(lo{g}_2(s))$ time where $s$ is the number of elements in Q$.$ Q$.$Insert$()$ adds one

element to $Q.$

Q$.$DeleteMin$()$ takes $(s)$ time where $s$ is the number of elements in $Q.$

Q$.$DeleteMin$()$ removes one element from $Q.$

Consider the following procedure whose input is an undirected graph G$.$ Edges G$.$E are represented by

an adjacency LIST.

weight $(v_i,v_j)$ is a positive weight assigned to edge $(v_i,v_j).$

weight $(v_i)$ is a positive weight assigned to vertex $(v_i).$

Let $n$ be the number of vertices of $G$ and let $m$ be the number of edges of $G.$

For this problem, assume that $mn.$

$($a$)$ Analyze lines $1-6$ of Proc$3$ giving a bound on their asymptotic running time in terms of $n$ and $m.$

$($b$)$ Analyze lines $7-13$ of Proc$3$ giving a bound on their asymptotic running time in terms of $n$ and $m.$

$($Note: Assume that $mn.)$

$($c$)$ Give the asymptotic running time of Proc$3$ in terms of $n$ and $m.$