# 2.10. Exercises¶

1. Give the Big O performance of the following code fragment:

for i in range(n):
for j in range(n):
k = 2 + 2

2. Give the Big O performance of the following code fragment:

for i in range(n):
k = 2 + 2

3. Give the Big O performance of the following code fragment:

i = n
while i > 0:
k = 2 + 2
i = i // 2

4. Give the Big O performance of the following code fragment:

for i in range(n):
for j in range(n):
for k in range(n):
k = 2 + 2

5. Give the Big O performance of the following code fragment:

for i in range(n):
k = 2 + 2
for j in range(n):
k = 2 + 2
for k in range(n):
k = 2 + 2

6. Devise an experiment to verify that the list index operator is $$O(1)$$.

7. Devise an experiment to verify that get item and set item are $$O(1)$$ for dictionaries.

8. Devise an experiment that compares the performance of the del operator on lists and dictionaries.

9. Given a list of numbers in random order, write an algorithm that works in $$O(n\log(n))$$ to find the $$k$$th smallest number in the list.

10. Can you improve the algorithm from the previous problem to be linear? Explain.