Give the best closed$-$form asymptotic bounds $($upper and lower$)$ that you can on

the following recurrence relations. You may assume that for any fixed constant, c$,$

T $($c$)$ in $\backslash$Theta $(1).$ Show your work.

$($a$)$ T $($n$)=$ T $($n $1)+\backslash$Theta $(1)$

$($b$)$ T $($n$)=$ T $($n $1)+$ O$($n$)$

$($c$)$ T $($n$)=$ T $($n$/2)+$ O$(1)$

$($d$)$ T $($n$)=$ T $($n$/2)+\backslash$Theta $($n$)$

$($e$)$ T $($n$)=2$T $($n$/2)+$ O$($n$)$

$($f$)$ T $($n$)=2$T $($n$/2)+$ O$(1)$

Give the best closed$-$form asymptotic bounds $($upper and lower$)$ that you can on

the following recurrence relations. You may assume that for any fixed constant, $c,$

$T(c)in(1).$ Show your work.

$($a$)T(n)=T(n-1)+(1)$

$($b$)T(n)=T(n-1)+O(n)$

$($c$)T(n)=T(\frac{n}{2})+O(1)$

$($d$)T(n)=T(\frac{n}{2})+(n)$

$($e$)T(n)=2T(\frac{n}{2})+O(n)$

$($f$)T(n)=2T(\frac{n}{2})+O(1)$