Big O Review

What's the best way?

How would you send data from São Paulo to Cape Town?

Previously...

Print all integer solutions to:

$a^3 + b^3 = c^3 + d^3$

for $a$, $b$, $c$, and $d$ between $1$ and $n$.

Source: Cracking the Coding Interview, p.68

$a^3 + b^3 = c^3 + d^3$


def print_solutions(n):
    for a in range(1, n+1):
        for b in range(1, n+1):
            for c in range(1, n+1):
                for d in range(1, n+1):
                    if a**3 + b**3 == c**3 + d**3:
                        print(a, b, c, d)


def print_solutions(n):
    for a in range(1, n+1):
        for b in range(1, n+1):
            for c in range(1, n+1):
                for d in range(1, n+1):
                    if a**3 + b**3 == c**3 + d**3:
                        O(1)


def print_solutions(n):
    for a in range(1, n+1):
        for b in range(1, n+1):
            for c in range(1, n+1):
                for d in range(1, n+1):
                    O(1)


def print_solutions(n):
    for a in range(1, n+1):
        for b in range(1, n+1):
            for c in range(1, n+1):
                O(n)


def print_solutions(n):
    for a in range(1, n+1):
        for b in range(1, n+1):
            O(n²)


def print_solutions(n):
    for a in range(1, n+1):
        O(n³)


def print_solutions(n):
    O(n⁴)

$a^3 + b^3 = c^3 + d^3$

Can we do better?


def print_solutions(n):
    for a in range(1, n+1):
        for b in range(1, n+1):
            for c in range(1, n+1):
                for d in range(1, n+1):
                    if a**3 + b**3 == c**3 + d**3:
                        print(a, b, c, d)


def print_solutions(n):
    for a in range(1, n+1):
        for b in range(1, n+1):
            for c in range(1, n+1):
                d == int((a**3 + b**3 - c**3)**(1/3))
                if a**3 + b**3 == c**3 + d**3:
                    print(a, b, c, d)


def print_solutions(n):
    for a in range(1, n+1):
        for b in range(1, n+1):
            for c in range(1, n+1):
                d == int((a**3 + b**3 - c**3)**(1/3))
                if a**3 + b**3 == c**3 + d**3:
                    O(1)


def print_solutions(n):
    for a in range(1, n+1):
        for b in range(1, n+1):
            for c in range(1, n+1):
                d == int((a**3 + b**3 - c**3)**(1/3))
                O(1)


def print_solutions(n):
    for a in range(1, n+1):
        for b in range(1, n+1):
            for c in range(1, n+1):
                O(1)
                O(1)


def print_solutions(n):
    for a in range(1, n+1):
        for b in range(1, n+1):
            for c in range(1, n+1):
                O(1) + O(1)


def print_solutions(n):
    for a in range(1, n+1):
        for b in range(1, n+1):
            for c in range(1, n+1):
                O(1)


def print_solutions(n):
    for a in range(1, n+1):
        for b in range(1, n+1):
            O(n)


def print_solutions(n):
    for a in range(1, n+1):
        O(n) * O(n)


def print_solutions(n):
    for a in range(1, n+1):
        O(n²)


def print_solutions(n):
    O(n) * O(n²)


def print_solutions(n):
    O(n³)

$a^3 + b^3 = c^3 + d^3$

Can we do better?


def print_solutions(n):
    for a in range(1, n+1):
        for b in range(1, n+1):
            for c in range(1, n+1):
                d == int((a**3 + b**3 - c**3)**(1/3))
                if a**3 + b**3 == c**3 + d**3:
                    print(a, b, c, d)


def print_solutions(n):
    results = {}
    for a in range(1, n+1):
        for b in range(1, n+1):
            result = a**3 + b**3
            results.setdefault(result, []).append((a, b))
    for c in range(1, n+1):
        for d in range(1, n+1):
            for a, b in results[c**3 + d**3]:
                print(a, b, c, d)


def print_solutions(n):
    results = {}
    for a in range(1, n+1):
        for b in range(1, n+1):
            result = a**3 + b**3
            r = results.setdefault(result, [])
            r.append((a, b))
    for c in range(1, n+1):
        for d in range(1, n+1):
            for a, b in results[c**3 + d**3]:
                print(a, b, c, d)


def print_solutions(n):
    results = {}
    for a in range(1, n+1):
        for b in range(1, n+1):
            O(1)
            r = results.setdefault(result, [])
            r.append((a, b))
    for c in range(1, n+1):
        for d in range(1, n+1):
            for a, b in results[c**3 + d**3]:
                print(a, b, c, d)


def print_solutions(n):
    results = {}
    for a in range(1, n+1):
        for b in range(1, n+1):
            O(1)
            O(1)
            r.append((a, b))
    for c in range(1, n+1):
        for d in range(1, n+1):
            for a, b in results[c**3 + d**3]:
                print(a, b, c, d)


def print_solutions(n):
    results = {}
    for a in range(1, n+1):
        for b in range(1, n+1):
            O(1)
            O(1)
            O(1)
    for c in range(1, n+1):
        for d in range(1, n+1):
            for a, b in results[c**3 + d**3]:
                print(a, b, c, d)


def print_solutions(n):
    results = {}
    for a in range(1, n+1):
        for b in range(1, n+1):
            O(1) + O(1) + O(1)


    for c in range(1, n+1):
        for d in range(1, n+1):
            for a, b in results[c**3 + d**3]:
                print(a, b, c, d)


def print_solutions(n):
    results = {}
    for a in range(1, n+1):
        for b in range(1, n+1):
            O(1) + O(1) + O(1)
    for c in range(1, n+1):
        for d in range(1, n+1):
            for a, b in results[c**3 + d**3]:
                print(a, b, c, d)


def print_solutions(n):
    results = {}
    for a in range(1, n+1):
        for b in range(1, n+1):
            O(1)
    for c in range(1, n+1):
        for d in range(1, n+1):
            for a, b in results[c**3 + d**3]:
                print(a, b, c, d)


def print_solutions(n):
    results = {}
    for a in range(1, n+1):
        O(n)

    for c in range(1, n+1):
        for d in range(1, n+1):
            for a, b in results[c**3 + d**3]:
                print(a, b, c, d)


def print_solutions(n):
    results = {}
    O(n) * O(n)


    for c in range(1, n+1):
        for d in range(1, n+1):
            for a, b in results[c**3 + d**3]:
                print(a, b, c, d)


def print_solutions(n):
    results = {}
    O(n²)


    for c in range(1, n+1):
        for d in range(1, n+1):
            for a, b in results[c**3 + d**3]:
                print(a, b, c, d)


def print_solutions(n):
    results = {}
    O(n²)


    for c in range(1, n+1):
        for d in range(1, n+1):
            for a, b in results[c**3 + d**3]:
                O(1)


def print_solutions(n):
    results = {}
    O(n²)


    for c in range(1, n+1):
        for d in range(1, n+1):
            O(m)  # m is the number of cube
                  # pairs with the same sum


def print_solutions(n):
    results = {}
    O(n²)


    for c in range(1, n+1):
        O(n) * O(m)
                  # m is the number of cube
                  # pairs with the same sum


def print_solutions(n):
    results = {}
    O(n²)


    for c in range(1, n+1):
        O(nm)
                  # m is the number of cube
                  # pairs with the same sum


def print_solutions(n):
    results = {}
    O(n²)


    O(n) * O(nm)

                  # m is the number of cube
                  # pairs with the same sum


def print_solutions(n):
    results = {}
    O(n²)


    O(n²m)

                  # m is the number of cube
                  # pairs with the same sum


def print_solutions(n):
    results = {}
    O(n²)
    O(n²m)
    # m is the number of cube
    # pairs with the same sum


def print_solutions(n):
    O(1)
    O(n²)
    O(n²m)
    # m is the number of cube
    # pairs with the same sum


def print_solutions(n):
    O(1) + O(n²) + O(n²m)


    # m is the number of cube
    # pairs with the same sum


def print_solutions(n):
    O(n²m)


    # m is the number of cube
    # pairs with the same sum

$1279 = 1^3 + 12^3 = 9^3 + 10^3$

Srinivasa Ramanujan and Godfrey Harold Hardy

\begin{aligned} Ta(1) = 2 &= 1^3 + 1^3 \\ Ta(2) = 1729 &= 1^3 + 12^3 \\ &= 9^3 + 10^3 \\ Ta(3) = 87539319 &= 167^3 + 436^3 \\ &=228^3 + 423^3 \\ &=255^3 + 414^3 \\ Ta(4) = 6963472309248 &= 2421^3 + 19083^3 \dots \\ Ta(5) = 48988659276962496 &= 38787^3 + 365757^3 \dots \\ \end{aligned} https://en.wikipedia.org/wiki/Taxicab_number

Ou seja,

m = O(1)

$a^3 + b^3 = c^3 + d^3$


def print_solutions(n):
    O(n²m)


def print_solutions(n):
    O(n²)

Quiz!

https://b.socrative.com/student

CODINT261

Question 1

What's the time complexity of the following code?


def foo(numbers: list[int]) -> None:
    sum_total = 0
    prod_total = 1
    for number in numbers:
        sum_total += number
    for number in numbers:
        prod_total *= number
    print(sum_total, prod_total)

a) $O(1)$	b) $O(\log n)$	c) $O(\sqrt{n})$	d) $O(n)$
e) $O(n\log n)$	f) $O(n^2)$	g) $O(2^n)$	h) $O(n!)$

a) $O(1)$	b) $O(\log n)$	c) $O(\sqrt{n})$	d) $O(n)$
e) $O(n\log n)$	f) $O(n^2)$	g) $O(2^n)$	h) $O(n!)$

Question 2

What's the time complexity of the following code?


def print_pairs(elements: list) -> None:
    for i in range(len(elements)):
        for j in range(len(elements)):
            print(elements[i], elements[j])

a) $O(1)$	b) $O(\log n)$	c) $O(\sqrt{n})$	d) $O(n)$
e) $O(n\log n)$	f) $O(n^2)$	g) $O(2^n)$	h) $O(n!)$

a) $O(1)$	b) $O(\log n)$	c) $O(\sqrt{n})$	d) $O(n)$
e) $O(n\log n)$	f) $O(n^2)$	g) $O(2^n)$	h) $O(n!)$

Question 3

What's the time complexity of the following code?


def print_pairs(elements: list) -> None:
    for i in range(len(elements)):
        for j in range(i+1, len(elements)):
            print(elements[i], elements[j])

a) $O(1)$	b) $O(\log n)$	c) $O(\sqrt{n})$	d) $O(n)$
e) $O(n\log n)$	f) $O(n^2)$	g) $O(2^n)$	h) $O(n!)$

a) $O(1)$	b) $O(\log n)$	c) $O(\sqrt{n})$	d) $O(n)$
e) $O(n\log n)$	f) $O(n^2)$	g) $O(2^n)$	h) $O(n!)$

Question 4

What's the time complexity of the following code?


def print_pairs(list_a: list, list_b: list) -> None:
    for i in range(len(list_a)):
        for j in range(len(list_b)):
            if list_a[i] < list_b[j]:
                print(list_a[i], list_b[j])

$O(ab)$

Question 5

What's the time complexity of the following code?


def print_pairs(elements: list) -> None:
    for i in range(len(elements)):
        for j in range(len(elements)):
            for k in range(100000):
                print(elements[i], elements[j])

a) $O(1)$	b) $O(\log n)$	c) $O(\sqrt{n})$	d) $O(n)$
e) $O(n\log n)$	f) $O(n^2)$	g) $O(2^n)$	h) $O(n!)$

a) $O(1)$	b) $O(\log n)$	c) $O(\sqrt{n})$	d) $O(n)$
e) $O(n\log n)$	f) $O(n^2)$	g) $O(2^n)$	h) $O(n!)$

The innermost for loop is $O(1)$

Question 6

What's the time complexity of the following code?


def revert(lst: list) -> None:
    for i in range(len(lst) // 2):
        other = lst[len(lst) - i - 1]
        lst[i], lst[other] = lst[other], lst[i]

a) $O(1)$	b) $O(\log n)$	c) $O(\sqrt{n})$	d) $O(n)$
e) $O(n\log n)$	f) $O(n^2)$	g) $O(2^n)$	h) $O(n!)$

a) $O(1)$	b) $O(\log n)$	c) $O(\sqrt{n})$	d) $O(n)$
e) $O(n\log n)$	f) $O(n^2)$	g) $O(2^n)$	h) $O(n!)$

$O(kn) = O(n)$ for any constant $k$

Question 7

Which of the following are equal to $O(n)$?

a) $O(n + p)$, $p < \frac{n}{2}$	b) $O(2n)$
c) $O(n + \log n)$	d) $O(n + m)$

a) $O(n + p)$, $p < \frac{n}{2}$	b) $O(2n)$
c) $O(n + \log n)$	d) $O(n + m)$

Question 8

Supose you have a function that receives an array of strings. Initially, we sort each string, and then we sort the array. What is the time complexity of your function?

Sort one string: $O(s \log s)$
Sort all strings: $O(a \cdot s \log s)$
Sort the array: $O(a \cdot s \log a)$
Total: $O(a \cdot s (\log a + \log s))$

Question 9

What's the time complexity of the following code?


def sum_r(root: TreeNode) -> int:
    if root is None:
        return 0
    return sum_r(root.left) + root.val + sum_r(root.right)

a) $O(1)$	b) $O(\log n)$	c) $O(\sqrt{n})$	d) $O(n)$
e) $O(n\log n)$	f) $O(n^2)$	g) $O(2^n)$	h) $O(n!)$

a) $O(1)$	b) $O(\log n)$	c) $O(\sqrt{n})$	d) $O(n)$
e) $O(n\log n)$	f) $O(n^2)$	g) $O(2^n)$	h) $O(n!)$

Binary tree does not necessarily imply logarithmic time!

Question 10

What's the time complexity of the following code?


def is_prime(n: int) -> bool:
    x = 2
    while x * x <= n:
        if n % x == 0:
            return False
        x += 1
    return True

a) $O(1)$	b) $O(\log n)$	c) $O(\sqrt{n})$	d) $O(n)$
e) $O(n\log n)$	f) $O(n^2)$	g) $O(2^n)$	h) $O(n!)$

a) $O(1)$	b) $O(\log n)$	c) $O(\sqrt{n})$	d) $O(n)$
e) $O(n\log n)$	f) $O(n^2)$	g) $O(2^n)$	h) $O(n!)$

The condition is equal to $x \leq \sqrt{n}$

Question 11

What's the time complexity of the following code?


def factorial(n: int) -> int:
    if n < 0:
        return -1
    if n == 0:
        return 1
    return n * factorial(n-1)

a) $O(1)$	b) $O(\log n)$	c) $O(\sqrt{n})$	d) $O(n)$
e) $O(n\log n)$	f) $O(n^2)$	g) $O(2^n)$	h) $O(n!)$

a) $O(1)$	b) $O(\log n)$	c) $O(\sqrt{n})$	d) $O(n)$
e) $O(n\log n)$	f) $O(n^2)$	g) $O(2^n)$	h) $O(n!)$

Question 12

What's the time complexity of the following code?


def fibo(n: int) -> int:
    if n <= 0:
        return 0
    if n == 1:
        return 1
    return fibo(n-1) + fibo(n-2)

a) $O(1)$	b) $O(\log n)$	c) $O(\sqrt{n})$	d) $O(n)$
e) $O(n\log n)$	f) $O(n^2)$	g) $O(2^n)$	h) $O(n!)$

a) $O(1)$	b) $O(\log n)$	c) $O(\sqrt{n})$	d) $O(n)$
e) $O(n\log n)$	f) $O(n^2)$	g) $O(2^n)$	h) $O(n!)$

Recursion: each function call makes other 2 calls

Question 13

What's the time complexity of the following code?


def all_fibo(n: int) -> None:
    for i in range(n):
        print(i, fibo(i))

def fibo(n: int) -> int:
    if n <= 0:
        return 0
    if n == 1:
        return 1
    return fibo(n-1) + fibo(n-2)

a) $O(1)$	b) $O(\log n)$	c) $O(\sqrt{n})$	d) $O(n)$
e) $O(n\log n)$	f) $O(2^n)$	g) $O(n!)$	h) $O(n 2^n)$

a) $O(1)$	b) $O(\log n)$	c) $O(\sqrt{n})$	d) $O(n)$
e) $O(n\log n)$	f) $O(2^n)$	g) $O(n!)$	h) $O(n 2^n)$

Question 14


def all_fibo(n: int) -> None:
    memo = [0 for i in range(n)]
    for i in range(n):
        print(i, fibo(i, memo))

def fibo(n: int, memo: list[int]) -> int:
    if n <= 1:
        return 0 if n < 1 else 1
    if memo[n] > 0:
        return memo[n]
    memo[n] = fibo(n-1, memo) + fibo(n-2, memo)
    return memo[n]

a) $O(1)$	b) $O(\log n)$	c) $O(\sqrt{n})$	d) $O(n)$
e) $O(n\log n)$	f) $O(2^n)$	g) $O(n!)$	h) $O(n 2^n)$

a) $O(1)$	b) $O(\log n)$	c) $O(\sqrt{n})$	d) $O(n)$
e) $O(n\log n)$	f) $O(2^n)$	g) $O(n!)$	h) $O(n 2^n)$

Question 15

What is the difference?


def pairs1(numbers):
    pairs = []
    for n1 in numbers:
        for n2 in numbers:
            p = (n1, n2)
            pairs.append(p)
    return pairs

NMBRS = list(range(100000))
for pair in pairs1(NMBRS):
    print(pair)


def pairs2(numbers):

    for n1 in numbers:
        for n2 in numbers:
            p = (n1, n2)

            yield p

NMBRS = range(100000)
for pair in pairs2(NMBRS):
    print(pair)

Question 16

What is the difference?


def fac1(n: int) -> int:
    if n < 0:
        return -1
    if n == 0:
        return 1
    return n * fac1(n-1)


def fac2(n: int) -> int:
    if n < 0:
        return -1
    f = 1
    while n > 1:
        f *= n
        n -= 1
    return f

Question 17


def greatest_odd(numbers: list[int]) -> int:
    numbers.sort(reverse=True)
    for n in numbers:
        if n % 2 == 1:
            return n
    return None

a) $O(1)$	b) $O(\log n)$	c) $O(\sqrt{n})$	d) $O(n)$
e) $O(n\log n)$	f) $O(2^n)$	g) $O(n!)$	h) $O(n 2^n)$

a) $O(1)$	b) $O(\log n)$	c) $O(\sqrt{n})$	d) $O(n)$
e) $O(n\log n)$	f) $O(2^n)$	g) $O(n!)$	h) $O(n 2^n)$

Sort is $O(n\log n)$

Data Structure Average Complexities

Name	Access	Search	Insert	Delete
Array	$O(1)$	$(n)$	$(n)$	$(n)$
Linked List	$O(n)$	$(n)$	$(1)$	$(1)$
Hash table	$O(1)$	$(1)$	$(1)$	$(1)$
Binary tree	$O(\log n)$	$(\log n)$	$(\log n)$	$(\log n)$

Sorting in general: $O(n\log n)$

"Hashtables: Arguably the single most important data structure known to mankind. You absolutely should know how they work. Be able to implement one using only arrays in your favorite language, in about the space of one interview."

Google Recruiting Team

Don't forget the pre-interview due next class!