ECS 32B – Introduction to Data Structures

Submit only one pdf filevia Gradescope. Do not submit a separate file for each problem. If you handwrite your solutions, make sure they are clear and readable.

Problem 1 (10 points each)

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 n0)

(1) def fun1 ( n ) :

x  =  0

for i in range ( 2 ,  n / 2 ) :

x  =  x  *  2

return x

(2) def fun2 ( 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 fun3 ( n ) :

x  =  0

i   =  2  *  n

while i  >=   1 :

x  =  x  —  i

i   =   i  —  1

return x