Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: Yooo932851

ECS 32B – Introduction to Data Structures
Homework 01
Due: Janurary 15, 2020, 5:00pm PST
Submit only one pdf file via 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
f o r i in range ( 2 , n / 2 ) :
x = x ∗ 2
r e t u r n x
(2) def fun2 ( n ) :
x = 0
f o r i in range ( n ) :
f o r j in range ( n ) :
f o r k in range ( 1 , n ) :
x = x + 1
r e t u r n x
(3) def fun3 ( n ) :
x = 0
i = 2 ∗ n
while i >= 1 :
x = x − i
i = i − 1
r e t u r n x

(4) def fun4 ( n ) :
x = n
f o r i in range ( n ∗ n ) :
x = x + 2
r e t u r n x
(5) # l s t i s a l i s t o f i n t e g e r s
def fun5 ( l s t ) :
x = 0
f o r y in l s t :
x = x + y
r e t u r n x