(*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.**

In [1]:

```
%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
```

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.

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.

$t(n) = 2 n + 6n \log(n) + 5$

In [ ]:

```
n = Symbol('n')
O = Function('O')
t = 2*n + 6*n*log(n) + 5
answer = O(n*log(n))
checkAnswer1_0(answer)
```

$t(n) = 10000$

In [ ]:

```
n = Symbol('n')
O = Function('O')
t = 1000
answer = # YOUR ANSWER HERE #
checkAnswer1_1(answer)
```

$t(n) = 3n + 4$

In [ ]:

```
n = Symbol('n')
O = Function('O')
t = 3*n + 4
answer = # YOUR ANSWER HERE #
checkAnswer1_2(answer)
```

$t(n) = 7n^2 + 100 n $

In [ ]:

```
n = Symbol('n')
O = Function('O')
t = 7*n**2 + 100*n
answer = # YOUR ANSWER HERE #
checkAnswer1_3(answer)
```

$t(n) = 13n + 12 n \log(n)$

In [ ]:

```
n = Symbol('n')
O = Function('O')
t = 13*n + 12*n*log(n)
answer = # YOUR ANSWER HERE #
checkAnswer1_4(answer)
```

$t(n) = 6n^3 + 13n^3 \log(n) + 8 n^2 + 9 n + 10000$

In [ ]:

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

$t(n) = 1 + 2 + 3 + \dots + n $

*This problem might be more difficult than the others. Don't be afraid to ask for help!*

In [ ]:

```
n = Symbol('n')
O = Function('O')
answer = # YOUR ANSWER HERE #
checkAnswer1_6(answer)
```

$t(n) = n^2 + (\log n)^2$

*This problem might be more difficult than the others. Don't be afraid to ask for help!*

In [ ]:

```
n = Symbol('n')
O = Function('O')
t = n**2 + (log(n))**2
answer = # YOUR ANSWER HERE #
checkAnswer1_7(answer)
```

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

```
b = 0 # 1 unit
for i in range(n): # Steps below are repeated n times
b += 1 # 1 unit
b *= 2 # 1 unit
```

In [ ]:

```
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
`b`

using 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)$.

```
a = 0
b = 10
a = b + 5
b += 10
```

In [ ]:

```
n = Symbol('n')
O = Function('O')
answer = # YOUR ANSWER HERE #
checkAnswer2_1(answer)
```

```
a = 0
for i in range(n):
a = a / 2
a = a * 3
```

In [ ]:

```
n = Symbol('n')
O = Function('O')
answer = # YOUR ANSWER HERE #
checkAnswer2_2(answer)
```

```
b = 0
for i in range(n // 2):
if i % 2 == 0:
b = b + 2
else:
b = b * 5
```

In [ ]:

```
n = Symbol('n')
O = Function('O')
answer = # YOUR ANSWER HERE #
checkAnswer2_3(answer)
```

```
c = 0
for i in range(n):
for j in range(n // 2):
c += (i * j)
for i in range(n):
c += i
```

In [ ]:

```
n = Symbol('n')
O = Function('O')
answer = # YOUR ANSWER HERE #
checkAnswer2_4(answer)
```

```
b = 0
for i in range(n):
for j in range(n):
for k in range(n):
b = (2 + j) % k
```

In [ ]:

```
n = Symbol('n')
O = Function('O')
answer = # YOUR ANSWER HERE #
checkAnswer2_5(answer)
```

```
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!*

In [ ]:

```
n = Symbol('n')
O = Function('O')
answer = # YOUR ANSWER HERE #
checkAnswer2_6(answer)
```

```
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!*

In [ ]:

```
n = Symbol('n')
O = Function('O')
answer = # YOUR ANSWER HERE #
checkAnswer2_7(answer)
```

```
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!*

In [ ]:

```
n = Symbol('n')
O = Function('O')
answer = # YOUR ANSWER HERE #
checkAnswer2_8(answer)
```

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.

Whose code has the better running time, in terms of Big-O?

In [ ]:

```
#
```

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*.

In [ ]:

```
#
```

In [ ]:

```
#
```

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*.

In [ ]:

```
#
```

In [2]:

```
n = Symbol('n')
O = Function('O')
answer = # YOUR ANSWER HERE #
checkAnswer5_1(answer)
```

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.*

In [ ]:

```
```