Lab 12a¶
(Created by Jabari Hastings and Tyler Hou)
Over the past couple of weeks, we've written several functions that perform various tasks. These functions or procedures are called algorithms. For any algorithm that you will write, you should hope to have the following guarantees:
- Correctness- The algorithm should fulfill its intended purpose
- Efficiency- The algorithm should be fast and use as little memory as possible
When we start to reason about the speed (or running time) of our algorithm, we are in the realm of time complexity. This lab should help you to become more confortable with this concept.
Please run the following cell before you proceed.
%pip install sympy
import sympy
from sympy import Symbol, Function, log, sympify
n = Symbol('n')
O = Function('O')
def f(globals, locals):
import base64
code = "ZGVmIGNyZWF0ZV9zb2x1dGlvbl9mdW5jdGlvbnMoKToKICAgIG4gPSBTeW1ib2woJ24nKQogICAgTyA9IEZ1bmN0aW9uKCdPJykKCiAgICBzb2x1dGlvbnMgPSB7CiAgICAgICAgIjFfMCIgOiBPKG4qIGxvZyhuKSksCiAgICAgICAgIjFfMSIgOiBPKDEpLAogICAgICAgICIxXzIiIDogTyhuKSwKICAgICAgICAiMV8zIiA6IE8obioqMiksCiAgICAgICAgIjFfNCIgOiBPKG4qbG9nKG4pKSwKICAgICAgICAiMV81IiA6IE8oKG4qKjMpKiBsb2cobikpLAogICAgICAgICIxXzYiIDogTyhuKioyKSwKICAgICAgICAiMV83IiA6IE8obioqMiksCiAgICAgICAgIjJfMCIgOiBPKG4pLAogICAgICAgICIyXzEiIDogTygxKSwKICAgICAgICAiMl8yIiA6IE8obiksCiAgICAgICAgIjJfMyIgOiBPKG4pLAogICAgICAgICIyXzQiIDogTyhuKioyKSwKICAgICAgICAiMl81IiA6IE8obioqMyksCiAgICAgICAgIjJfNiIgOiBPKG4qKjIpLAogICAgICAgICIyXzciIDogTyhsb2cobikpLAogICAgICAgICIyXzgiIDogTyhuICogbG9nKG4pKSwKICAgICAgICAiNV8xIiA6IE8obiksCiAgICB9CgoKICAgIGRlZiBtYWtlX3NvbHV0aW9uX2Z1bmN0aW9uKGNvcnJlY3RfYW5zd2VyKToKICAgICAgICBkZWYgc29sdXRpb25fZnVuY3Rpb24oYW5zd2VyKToKICAgICAgICAgICAgaW1wb3J0IG1hdGgKICAgICAgICAgICAgbiA9IFN5bWJvbCgnbicpCiAgICAgICAgICAgIGFuc3dlciA9IHN5bXBpZnkoYW5zd2VyKS5yZXBsYWNlKE8sIGxhbWJkYSB4OiB4KQogICAgICAgICAgICBjb3JyZWN0ID0gY29ycmVjdF9hbnN3ZXIucmVwbGFjZShPLCBsYW1iZGEgeDogeCkKICAgICAgICAgICAgaWYgY29ycmVjdC5lcXVhbHMoYW5zd2VyKToKICAgICAgICAgICAgICAgIHByaW50KCJUZXN0IGNhc2UgcGFzc2VkISIpCiAgICAgICAgICAgICAgICByZXR1cm4KCiAgICAgICAgICAgIHJlc3VsdHMgPSBbXQogICAgICAgICAgICBmb3IgZXhwIGluIHJhbmdlKDEwLCAxMTAsIDEwKToKICAgICAgICAgICAgICAgIHZhbCA9IDEwICoqIGV4cAogICAgICAgICAgICAgICAgcmF0aW8gPSAoYW5zd2VyLnN1YnMobiwgdmFsKSAvIGNvcnJlY3Quc3VicyhuLCB2YWwpKQogICAgICAgICAgICAgICAgcmVzdWx0cy5hcHBlbmQobG9nKHJhdGlvKS5ldmFsZigpKQogICAgICAgICAgICBpbmYsIHN1cCA9IG1pbihyZXN1bHRzKSwgbWF4KHJlc3VsdHMpCiAgICAgICAgICAgIGlmIG1hdGguaXNjbG9zZShpbmYsIHN1cCk6CiAgICAgICAgICAgICAgICBpZiBtYXRoLmlzY2xvc2UoaW5mLCAwKToKICAgICAgICAgICAgICAgICAgICBwcmludCgiVGVzdCBjYXNlIHBhc3NlZCEiKQogICAgICAgICAgICAgICAgZWxzZToKICAgICAgICAgICAgICAgICAgICBwcmludCgiLS0tLS0tLS0tLS0tLS0tLSBUZXN0IGNhc2UgZmFpbGVkLiAtLS0tLS0tLS0tLS0tLS0tIikKICAgICAgICAgICAgICAgICAgICBwcmludChmIlZlcnkgY2xvc2UhIFRoZSBhbnN3ZXIgeW91IHByb3ZpZGVkLCB7cmVwcihhbnN3ZXIpfSwiKQogICAgICAgICAgICAgICAgICAgIHByaW50KCJkaWZmZXJzIGZyb20gdGhlIGNvcnJlY3QgYW5zd2VyIGJ5IGEgY29uc3RhbnQgZmFjdG9yLiIpCiAgICAgICAgICAgICAgICAgICAgcHJpbnQoIi0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLSIpCiAgICAgICAgICAgICAgICAgICAgcHJpbnQoKQogICAgICAgICAgICBlbHNlOgogICAgICAgICAgICAgICAgcHJpbnQoIi0tLS0tLS0tLS0tLS0tLS0gVGVzdCBjYXNlIGZhaWxlZC4gLS0tLS0tLS0tLS0tLS0tLSIpCiAgICAgICAgICAgICAgICBpZiByZXN1bHRzWy0xXSA8IDE6CiAgICAgICAgICAgICAgICAgICAgcHJpbnQoZiJUaGUgYW5zd2VyIHlvdSBwcm92aWRlZCwge3JlcHIoYW5zd2VyKX0sIGdyb3dzIG11Y2giKQogICAgICAgICAgICAgICAgICAgIHByaW50KCJtb3JlIHNsb3dseSB0aGFuIHRoZSBjb3JyZWN0IGFuc3dlci4iKQogICAgICAgICAgICAgICAgZWxpZiByZXN1bHRzWy0xXSA+IDE6CiAgICAgICAgICAgICAgICAgICAgcHJpbnQoZiJUaGUgYW5zd2VyIHlvdSBwcm92aWRlZCwge3JlcHIoYW5zd2VyKX0sIGdyb3dzIG11Y2giKQogICAgICAgICAgICAgICAgICAgIHByaW50KCJtb3JlIHF1aWNrbHkgdGhhbiB0aGUgY29ycmVjdCBhbnN3ZXIuIikKICAgICAgICAgICAgICAgIHByaW50KCItLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0iKQogICAgICAgICAgICAgICAgcHJpbnQoKQogICAgICAgIHJldHVybiBzb2x1dGlvbl9mdW5jdGlvbgoKICAgIGdsb2JhbHNfID0gZ2xvYmFscygpCiAgICBmb3IgcXVlc3Rpb24sIHNvbHV0aW9uIGluIHNvbHV0aW9ucy5pdGVtcygpOgogICAgICAgIG5hbWUgPSBmImNoZWNrQW5zd2Vye3F1ZXN0aW9ufSIKICAgICAgICBmbiA9IG1ha2Vfc29sdXRpb25fZnVuY3Rpb24oc29sdXRpb24pCiAgICAgICAgZm4uX19uYW1lX18gPSBuYW1lCiAgICAgICAgZ2xvYmFsc19bbmFtZV0gPSBmbgoKICAgICAgICAKY3JlYXRlX3NvbHV0aW9uX2Z1bmN0aW9ucygpCg=="
exec(base64.b64decode(code), globals, locals)
f(globals(), locals())
del f
Problem 1¶
When we are analyzing the time complexity of an algorithm, we care about how the running time depends on the size of the input. In the examples that follow, we'll typically let $n$ represent the input size and let $t(n)$ represent the running time.
Big-O notation¶
Suppose we know that a few lines of code take time $t(n)$ to be executed. We can try the following procedure to find the Big-O notation:
- Find the term with the largest exponent on $n$ (this called the "highest order term."). Suppose that exponent is $a$.
- If the largest exponent is $a$ and there are multiple terms with this exponent, see if any terms multiply $n^a$ by $\log{n}$. Take the term with the highest exponent on $\log{n}$.
- The runtime of the function is that term with no constant.
As a hint, we have the following rule $$ 1 \leq \log(n) \leq n \leq n \log (n) \leq n^2 \leq n^2 \log n \leq n^3 \leq n^3 \log n \leq ...$$
Now, let's try several exercises. For each of the expressions below, provide the big-Oh notation.
1.0 Example¶
$t(n) = 2 n + 6n \log(n) + 5$
n = Symbol('n')
O = Function('O')
t = 2*n + 6*n*log(n) + 5
answer = O(n*log(n))
checkAnswer1_0(answer)
1.1¶
$t(n) = 10000$
n = Symbol('n')
O = Function('O')
t = 1000
answer = # YOUR ANSWER HERE #
checkAnswer1_1(answer)
1.2¶
$t(n) = 3n + 4$
n = Symbol('n')
O = Function('O')
t = 3*n + 4
answer = # YOUR ANSWER HERE #
checkAnswer1_2(answer)
1.3¶
$t(n) = 7n^2 + 100 n $
n = Symbol('n')
O = Function('O')
t = 7*n**2 + 100*n
answer = # YOUR ANSWER HERE #
checkAnswer1_3(answer)
1.4¶
$t(n) = 13n + 12 n \log(n)$
n = Symbol('n')
O = Function('O')
t = 13*n + 12*n*log(n)
answer = # YOUR ANSWER HERE #
checkAnswer1_4(answer)
1.5¶
$t(n) = 6n^3 + 13n^3 \log(n) + 8 n^2 + 9 n + 10000$
n = Symbol('n')
O = Function('O')
t = 6*n**3 + (13*n**3)*log(n) + 8*n**2 + 9*n + 10000
answer = # YOUR ANSWER HERE #
checkAnswer1_5(answer)
1.6¶
$t(n) = 1 + 2 + 3 + \dots + n $
This problem might be more difficult than the others. Don't be afraid to ask for help!
n = Symbol('n')
O = Function('O')
answer = # YOUR ANSWER HERE #
checkAnswer1_6(answer)
1.7¶
$t(n) = n^2 + (\log n)^2$
This problem might be more difficult than the others. Don't be afraid to ask for help!
n = Symbol('n')
O = Function('O')
t = n**2 + (log(n))**2
answer = # YOUR ANSWER HERE #
checkAnswer1_7(answer)
Problem 2¶
In this problem, you will see several pieces of code that will depend on the variables n. For each snippet, give the running time using big-O notation. Please simplify your answer as much as possible.
(You can assume that any line containing math operations and assignment of variables takes 1 unit of time)
Example¶
b = 0 # 1 unit
for i in range(n): # Steps below are repeated n times
b += 1 # 1 unit
b *= 2 # 1 unit
n = Symbol('n')
O = Function('O')
answer = # YOUR ANSWER HERE #
checkAnswer2_0(answer)
Here's why we said our answer is $O(n)$.
- The first line of code is just assigning variables, which takes constant time, $O(1)$.
- Inside the first loop we are updating the variable
busing basic math operations, which takes constant time. We are doing these updates $n$ times, so the loop takes time $n \times O(1) = O(n)$.
Putting it all together, the code takes time $O(1) + O(n) = O(n)$.
2.1¶
a = 0
b = 10
a = b + 5
b += 10
n = Symbol('n')
O = Function('O')
answer = # YOUR ANSWER HERE #
checkAnswer2_1(answer)
2.2¶
a = 0
for i in range(n):
a = a / 2
a = a * 3
n = Symbol('n')
O = Function('O')
answer = # YOUR ANSWER HERE #
checkAnswer2_2(answer)
2.3¶
b = 0
for i in range(n // 2):
if i % 2 == 0:
b = b + 2
else:
b = b * 5
n = Symbol('n')
O = Function('O')
answer = # YOUR ANSWER HERE #
checkAnswer2_3(answer)
2.4¶
c = 0
for i in range(n):
for j in range(n // 2):
c += (i * j)
for i in range(n):
c += i
n = Symbol('n')
O = Function('O')
answer = # YOUR ANSWER HERE #
checkAnswer2_4(answer)
2.5¶
b = 0
for i in range(n):
for j in range(n):
for k in range(n):
b = (2 + j) % k
n = Symbol('n')
O = Function('O')
answer = # YOUR ANSWER HERE #
checkAnswer2_5(answer)
2.6¶
d = 0
c = 2
for i in range(n):
for j in range(i):
d += 1
c = 3
This problem might be more difficult than the others. Don't be afraid to ask for help!
n = Symbol('n')
O = Function('O')
answer = # YOUR ANSWER HERE #
checkAnswer2_6(answer)
2.7¶
x = n
while x > 1:
a = 2
b = a * 3
x //= 2
This problem might be more difficult than the others. Don't be afraid to ask for help!
n = Symbol('n')
O = Function('O')
answer = # YOUR ANSWER HERE #
checkAnswer2_7(answer)
2.8¶
a = 12
b = 13
for i in range(n):
for j in range(100):
a = b + 5
b = 10
for i in range(int(log(n))):
a += 2
This problem might be more difficult than the others. Don't be afraid to ask for help!
n = Symbol('n')
O = Function('O')
answer = # YOUR ANSWER HERE #
checkAnswer2_8(answer)
Problem 3¶
Annamira and Nadia were asked to write a function that sorts a list of items. Annamira wrote a function with a running time of $O(n^2)$. Nadia, on the other hand, wrote a function with a running time of $O(n \log (n))$. In both cases, $n$ denotes the length of the list.
3.1¶
Whose code has the better running time, in terms of Big-O?
#
3.2¶
It turns out that the running time of Annamira's function is $t(n) = 0.0001 n^2$ and the running time of Nadia's function is $t(n) = 10 n \log (n)$. Give a value of $n$ that will make Annamira's function run faster than Nadia's. Write your answer as a comment.
#
#
4.2¶
Consider the function $t(n) = \log (n^n)$. Now, Jabari is trying to convince Tyler that $t(n) = O(\log n)$. Is Jabari correct? Write your answer as a comment.
#
n = Symbol('n')
O = Function('O')
answer = # YOUR ANSWER HERE #
checkAnswer5_1(answer)
5.2¶
In lecture, we have written recursive algorithms for binary search and selection sort. For each of these algorithms, express the running time as a recurrence relation.
Hint: Your recurrence should have at least two parts: one for the base case and another for the recursive case.