The following function helps you test your code:
# RUN THIS BLOCK OF CODE BEFORE RUNNING ANY CELLS
def check_test(actual, expected):
if expected != actual:
print(f"Function should return the value {expected}, it is returning the value {actual}")
else:
print(f"Congratulations, the test case passed!")
The following function helps you time your code:
import time
def timer(func, *args):
start = time.perf_counter()
result = func(*args)
args_str = ', '.join([str(arg) for arg in args])
end = time.perf_counter()
print(f"Time to run function {func.__name__}({args_str}): {end - start:.5f} seconds")
return result
result = timer(sorted, range(1000000))
Time to run function sorted(range(0, 1000000)): 0.04210 seconds
Consider the following loop
for i in range(len(n)):
for j in range(len(n)):
for k in range(len(n)):
print(i, k, j)
If you run the above code with n = 1000 how many times does the function call print ?
# Write your answer in English, or use code to answer the question
Let's go back to fibonacci for a second.
Assume fib(n)
only gets n >= 0
.
def fib(n):
if n <= 1:
return 1
return fib(n-1) + fib(n-2)
Try running values fib(10)
, fib(15)
, fib(20)
, ... and see how long it takes for each of the cases.
fib10 = timer(fib, 10) # The `timer` function calls the `fib` function with the argument 10 for you
fib15 = timer(fib, 15)
fib20 = timer(fib, 20)
fib25 = timer(fib, 25)
fib30 = timer(fib, 30)
fib35 = timer(fib, 35)
Time to run function fib(10): 0.00003 seconds Time to run function fib(15): 0.00026 seconds Time to run function fib(20): 0.00264 seconds Time to run function fib(25): 0.02698 seconds Time to run function fib(30): 0.28283 seconds Time to run function fib(35): 2.88948 seconds
# do you think we can finish `fib(100)`? Why or why not?
# timer(fib, 100)
Explain your observation below interms of time complexity. How many recursive function calls do we need to solve for each of the cases above?
# Your answer here in English. Please check your answer with the
# person next to you, or ask a TA if you are unsure!
Write the time complexity of the following program in terms of $j$.
def loop(k):
for i in range(k):
print(i)
for j in range(10):
loop(j)
Your answer here:
4.1. If an algorithm has a time complexity of $O(n)$, what would the time complexity be if $n$ doubles? Select one:
A. It would be $O(n)$
B. It would be $O(n^2)$
C. It would be $O(2n)$
D. It would be $O(1)$
4.2. What is the time complexity of an algorithm that checks if an item exists in an unsorted list?
A. $O(n)$
B. $O(n^2)$
C. $O(1)$
D. $O(\log(n))$
4.3. If an algorithm's time complexity is $O(n^2)$ and it takes 1 second to process 1000 elements, approximately how long will it take to process 2000 elements?
A. 2 seconds
B. 4 seconds
C. 8 seconds
D. 16 seconds
4.4. What is the time complexity of finding the smallest or largest item in an unsorted list?
A. $O(n)$
B. $O(n^2)$
C. $O(1)$
D. $O(\log(n))$
4.5. What is the time complexity of a recursive Fibonacci algorithm?
5.1. Write a Python function to calculate the factorial of a number (n!) using both iterative and recursive approaches. What is the time complexity of each approach?
def factorial_iterative(n):
# TODO: Your code here
pass
def factorial_recursive(n):
# TODO: Your code here
pass
fac1000_iter = timer(factorial_iterative, 1000)
fac1000_rec = timer(factorial_recursive, 1000)
Time to run function factorial_iterative(1000): 0.00000 seconds Time to run function factorial_recursive(1000): 0.00000 seconds
5.2. Write a Python function that takes in a list of numbers and returns a new list with only the unique numbers (i.e., remove duplicates). What is the time complexity of your function?
def remove_duplicates(lst) -> list:
# TODO: Your code here
return []
length = 1000000
dup_list = list(range(length)) + list(range(length))
uniq_list = remove_duplicates(dup_list)
print('Test passed:', sorted(uniq_list) == sorted(range(length)))
Test passed: False
5.3. Write a Python function that accepts two strings and checks if one is a permutation of the other. What is the time complexity of your function?
def is_permutation(str1, str2) -> bool:
# TODO: Your code here
pass
print(is_permutation("abc", "cba"))
None
You are given a large, sorted list of integers, where each integer appears exactly twice except for one element that appears only once.
Implement a function called find_unique_element
that takes in this sorted list as input and returns the unique element.
For example, given the sorted list[1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6]
, the function should return 4
since it is the only element that appears once in the list.
Let's start with a linear time solution below:
def find_unique_element(array):
# WRITE YOUR CODE HERE
pass
check_test(find_unique_element([1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6]), 4)
check_test(find_unique_element([1]), 1)
check_test(find_unique_element([3, 4, 4]), 3)
check_test(find_unique_element([1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6]), 6)
Function should return the value 4, it is returning the value None Function should return the value 1, it is returning the value None Function should return the value 3, it is returning the value None Function should return the value 6, it is returning the value None
Challenge: Can you implement this function in $O(\log(n))$ time complexity?
Hint: Use binary search. What happens when the middle element is the same as the left or the right element? What happens when the middle element is different from both the left and right elements?
def find_unique_element_binary_search(array):
# WRITE YOUR CODE HERE
pass
check_test(find_unique_element_binary_search([1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6]), 4)
check_test(find_unique_element_binary_search([1]), 1)
check_test(find_unique_element_binary_search([3, 4, 4]), 3)
check_test(find_unique_element_binary_search([1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6]), 6)
Function should return the value 4, it is returning the value None Function should return the value 1, it is returning the value None Function should return the value 3, it is returning the value None Function should return the value 6, it is returning the value None