What is the Big$-\backslash$Theta $($tight bound$)$ of the func$()$ below as a function of n assuming that the

func$1($n$)$ is Big$-\backslash$Theta $($n$)?$ Prove your answer.

Algorithm $1$

def func$($n$)$:

j $=$ n

while j $>=1$:

for i in range$($j$)$:

val $=$ func$1($n$)$

j $=$ j$//3$

$2.$ Determine the Big$-\backslash$Theta complexity of func$2()$ as a function of n assuming the task$($a$,$b$)$ is

O$(1).$ Prove your answer. Use sigma notation $(\backslash$Sigma $).$

Algorithm $2$

def func$2($n$)$:

for i in range$(1,$ n $+1)$:

for j in range$($i$,1+($i $$ n$))$:

task$($i $+1,$ j$)$

$3.$ Let k be a positive integer. Prove that the Big$-$O $($upper bound$)$ of the following expression

is O$($nk$+1)$: $1$k $+2$k $+3$k $++$ nk$.$