We continued discussing complexity. Then we discussed higher-order, lambda expressions, $m$-channel merge and binary search.
from IPython.core.interactiveshell import InteractiveShell
InteractiveShell.ast_node_interactivity = "all"
Given two functions $f(n)$ and $g(n)$,
$f(n) = O(g(n))$
If and only if there exist $c > 0 $ and $n_{0}\in \mathbb{R}$ such that
$\forall n>n_0$
$|f(n)| \leq c\cdot|g(n)|$
Let $n$ denote the input size. Let $f_1(n) = O(g_1(n))\;$ and $f_2(n)=O(g_2(n))$.
for i in range(f1(n))):
O(1)
for j in range(f2(n)):
O(1)
Last week we proved that $f_1(n) + f_2(n) = O(g_1(n) + g_2(n))$ and that $f_1(n) + f_2(n) = O(max(g_1(n), g_2(n)))$
We've also mentioned that $f_1 + f_2 + ... + f_k = O(f_{max})$. That is, in a finite constant sum of functions, the dominate function defines the growth rate. A private case (which we have also proven last week) is that of a polynomial.
for i in range(f1(n)):
for j in range(f2(n)):
O(1)
Similar to the previous claim, it holds that $f_1(n) \cdot f_2(n) = O(g_1(n) \cdot g_2(n))$ (prove this yourself!).
for i in range(n):
for j in range(f(i)):
O(1)
Use $\sum$ to bound the time complexity in this case
Two useful examples:
for i in range(1, n + 1):
j = 1
while j <= n:
j += 1 # O(n**2)
j += 7 # O(n**2), inner loop does n/7 iterations
# for each outer loop
j *= 2 # O(n*log(n))
j *= 7 # O(n*log(n)), change log bases is like
# multiplying by a constant
j **= 2 # O(n*log(log(n))), Here we assume j starts from 2.
# by induction after k steps j = 2^(2^k)
# we need to take a log on both sides *twice*: n = 2^(2^k) => k = log log n
j += i # O(n*log(n)), h(n) = the sum of 1/i from i=1 to n is O(log(n))
# This is the harmonic series
Anonymous vs. named values
print(2**10)
x = 2**10
print(x)
1024 1024
Lambda expressions can be used for creating anonymous functions (and named ones as well)
(lambda x: x+2)(3)
plus2 = lambda x : x + 2
plus2(3)
5
5
def make_pow(n):
def fixed_pow(x):
return pow(x, n)
return fixed_pow
square = make_pow(2)
cube = make_pow(3)
square(10)
cube(10)
make_pow(2)(10)
100
1000
100
def make_pow(n):
return lambda x : pow(x, n)
square = make_pow(2)
cube = make_pow(3)
square(10)
cube(10)
100
1000
lst = ["michal", "amirrub", "noam", "ori", "elhanan"]
sorted(lst)
['amirrub', 'elhanan', 'michal', 'noam', 'ori']
"sorted" can recieve a function as an argument and use it to sort the input list. The function is given as the "key" argument to "sorted". Note that the "key" is used for ordering the elements without changing them.
examples: sort by length, sort by reverse lexicographical order
lst = ["michal", "amirrub", "noam", "ori", "elhanan"]
print(sorted(lst, key=lambda x: len(x)))
print(sorted(lst, key=len))
['ori', 'noam', 'michal', 'amirrub', 'elhanan'] ['ori', 'noam', 'michal', 'amirrub', 'elhanan']
What happens when two elements are equivalent under the key function? Will Python use the "builtin" comparison method? What if it's undefined?
# Here "x" should come before "y" lexicographically
lst1 = ["abc", "123", "x", "y"]
lst2 = ["abc", "123", "y", "x"]
print(sorted(lst1, key=lambda x: len(x)))
print(sorted(lst2, key=lambda x: len(x)))
['x', 'y', 'abc', '123'] ['y', 'x', 'abc', '123']
def sum_naturals(n):
total = 0
for k in range(1, n + 1):
total += k
return total
print(sum_naturals(10))
55
def sum_squares(n):
total = 0
for k in range(1, n + 1):
total += k**2
return total
print(sum_squares(10))
385
Let's make it a general function that gets another function as a parameter:
def summation(n, func):
total = 0
for k in range(1, n + 1):
total += func(k)
return total
The equivalent to sum_naturals and sum_squares:
term_naturals = lambda x : x
print(summation(10, term_naturals))
55
term_squares = lambda x : x**2
print(summation(10, term_squares))
385
Given a list of $m\geq 2$ sorted sublists (ascending) as an input, we would like to return as an output a new single sorted (ascending) list containing all elements in the input sublists. The input list/sublists should not be changed.
For complexity anaysis, we denote by $n$ the maximal length of an input sublist.
We will consider 3 possible solutions (two in class and one in hw3):
def multi_merge_v1(lst_of_lsts):
all_elems = [e for lst in lst_of_lsts for e in lst]
merged = []
while all_elems != []:
minimum = min(all_elems)
merged += [minimum]
all_elems.remove(minimum)
return merged
multi_merge_v1([[1, 2, 2, 3], [2, 3, 5], [5]])
[1, 2, 2, 2, 3, 3, 5, 5]
$mn$ iterations, in iteration $i$ we perform operations that take $O(mn-i)$. Overall complexity is $\sum_{i=0}^{mn}{(mn-i)} = \sum_{i=0}^{mn}(i) = O(m^2n^2)$
def merge(A, B):
""" merging two lists into a sorted list
A and B must be sorted! """
n = len(A)
m = len(B)
C = [None for i in range(n + m)]
a = b = c = 0
while a < n and b < m: #more element in both A and B
if A[a] < B[b]:
C[c] = A[a]
a += 1
else:
C[c] = B[b]
b += 1
c += 1
C[c:] = A[a:] + B[b:] #append remaining elements (one of those is empty)
return C
def multi_merge_v2(lst_of_lsts):
m = len(lst_of_lsts)
merged = []
for lst in lst_of_lsts:
merged = merge(lst, merged)
return merged
multi_merge_v2([[1, 2, 2, 3], [2, 3, 5], [5]])
[1, 2, 2, 2, 3, 3, 5, 5]
The function does $m$ iterations, in iteration $i$ we merge a list of length at most n with a list of length at most $n\cdot (i-1)$. Merging two lists of length $k,\ell$ takes $O(k + \ell)$. Overall complexity is at most $$\sum_{i=0}^{m} n\cdot(i-1) + n = \sum_{i=0}^{m}{ni} = n\cdot\sum_{i=0}^{m}i = O(nm^2)$$