$6.(10$ pts$)$ Derive the runtime of the following loop structure as a function of n and

determine its Big$-$O upper bound. You must show the derivation of the end result.

Simply stating the final answer without any derivation steps will result in zero points.

Assume atomic operations take unit time.

$2$

for $($i $=1$; i $<=$ n; i$++)$

$\{$

for $($jn; j $>=1$; j$--)$

$\{$

for $($k $=1$; k $<=$ i $+$ j; k$++)$

$\{$

$//$ some constant number of atomic operations

$\}//$ end k

$\}//$ end j

$\}//$ end i

$6.(10$ pts$)$ Derive the runtime of the following loop structure as a function of n and

determine its Big$-$O upper bound. You must show the derivation of the end result.

Simply stating the final answer without any derivation steps will result in zero points.

Assume atomic operations take unit time.

$2$

i $=$ n;

while $(>=2)$

$\{$

for $($j $=1$; j $<=$ i; j$++)$

$\{$

$//$ some constant number of atomic elementary operations

$\}//$ end j

i $=$ i $/2$;

$\}//$end while