$6$:$07$ C

Back HomeWork$1.$pdf

For each of the following functions, do the following:

Calculate $T(n),$ making sure not to discard constants or low$-$order terms yet $($you may or may not count the counting variable in a for loop$)$

Given what you think is the Big$-$O performance for the function

Prove that your proposed Big$-$O for the function is correct $($make sure to show your work; do not just provide values for $c$ and $n_0)$

$(1)$

def fun$1(n)$ :

$x=0$

for $iin$ range $(2,\frac{n}{2})$ :

$,x=x**2$

return $x$

$(2)$

def fun$2(n)$:

$x=0$

for $i$ in range$(n$ :

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

for $k$ in range $(1,n)$

$x=x+1$

return $x$

$(3)$

def fun$3(n)$ :

$x=0$

$i=2**n$

while $i1$:

$x=x-i$

$i=i-1$

return $x$

$1$

$(4)$

def fun$4($n$)$:

$x=n$

for $i$ in range $(n**n)$ :

$x=x+2$

return $x$

$(5)$

# lst is a list of integers

def fun$5(1$st$)$:

$x=0$

for $y$ in lst:

$x=x+y$

return $x$

Problem $2(10$ points each$)$

Suppose an algorithm solves a problem of input size $n$ in at most the number of steps listed for each $T(n)$ given below. Calculate the Big$-($not just Big$-$O$)$ for each $T(n).$ Show your work, including values for $c$ and $n_0.$

$(1)T(n)=10$

$(2)T(n)=2n^3+1$

$(3)T(n)=n^4+2n^2+nlogn$

$(4)T(n)=log(52^n)$

$(5)T(n)=3n^{2}logn$

$(1)$

$1$

Dashboard

Calendar

To Do Notifications

Inbox