What is the time complexity of the following piece of code? Check all that apply:

function unknown $($int n$)\{$

int i$,$ j;

int sum $=0$;

for $($i $=1$; i $<=$ n; i $*=2)\{$

for $($j $=0$; j $<$ i; j$++)\{$

sum $+=$ j;

$\}$

$\}$

return sum;

$\}$

Group of answer choices

$\backslash$Theta $($n$)$

o$($logn$)$

$\backslash$Omega $($logn$)$

$\backslash$Theta $($n$^2)$

O$($n$^2*$logn$)$

o$($n$)$

$\backslash$omega $($logn$)$

$\backslash$omega $($n$)$

O$($n$*$logn$)$

O$($logn$)$

$\backslash$Theta $($n$^2*$logn$)$

O$($n$^2)$

$\backslash$Omega $($n$^2*$logn$)$

$\backslash$Theta $($n$*$logn$)$

o$($n$*$logn$)$

$\backslash$Theta $($logn$)$

$\backslash$Omega $($n$^2)$

$\backslash$omega $($n$*$logn$)$

$\backslash$Omega $($n$*$logn$)$

$\backslash$Omega $($n$)$

O$($n$)$

Here$$s the best way to solve it$.$

Expert$-$verified

Share

$(0)$

$//$lets analyze the given code to find time complexity

int i$,$ j;$//$runs in constant time so : O$(1)$

int sum $=0$;$//$runs in constant time so : O$(1)$

for $($i $=1$; i $<=$ n; i $*=2)//$runs for i$=1$ to n$,$ each time i is multiplied by $2,$ so runs for $2^$k $=$ n$,$ k$=$logn times$//$base is $2$

$\{$

for $($j $=0$; j $<$ i; j$++)//$runs for i times

$\{$

$//$possible value of i: $1,2^1,2^2,2^3,...,2^$k

sum $+=$ j;$//$so runs for : $1+2^1+2^2+2^3+...+2^$k $=2^($k$+1)-1=(2*$k$)*2-1=2*$logn $-1$

$\}$

$\}$

return sum;$//$runs in constant time so : O$(1)$

$\}$

overall run time : $1+1+2*$logn$-1+1=2*$logn$+2=$ theta$($logn$)$

note: theta$($logn$)$ means both bigOh$($logn$)$ and bigOmega$($logn