#!/usr/bin/env python # coding: utf-8 #

cs1001.py , Tel Aviv University, Spring 2019

# # #### Recitation 4 # ### Complexity # # We analyzed the time complexity of different solutions for a given problem. # Then, we proved several claims using the Formal definition of Big O. # # #### Takeaways: # #
    #
  1. The time complexity bound implies how that the running time changes as a function of the input size.
    2. #
  2. Two solutions that have the same time complexity bound may differ in their running time (one can be more efficient than the other).
    3. #
  3. The Big O notation "hides" additive and multiplicative constants
    4. #
  4. Two solutions that have the same time complexity bound may differ in their running time (one can be more efficient than the other).
    5. #
  5. To analyze nested loops that are dependent, use a sum ($\sum$), with the boundaries of the external loop as the limits and the number of iterations for the inner loop in the sum itself.
    6. #
# _________________________________________________________________________________ # ### Problem: # Given a natural number $p$, how many right triangles exist with integer-sized sides whose perimeter is $p$? # # #### or in other words: # How many triplets $(a,b,c)$ are there such that: #
    #
  1. $a^2 +b^2 == c^2$
    2. #
  2. $a + b + c == p$
    3. #
  3. $a,b,c > 0$ are all integers
    4. #
# In order to avoid counting a triplet twice or more, we require that $0 < a < b < c$ # Note that: #
    #
  1. $a \neq b$ and $b \neq c$
    2. #
  2. The case $a = b$ cannot hold as this would imply $2a^2 = c^2 \implies c = \sqrt{2} a$
    3. #
  3. The condition $b < c$ is redundant (since we require that $a,b,c > 0$ and $a^2 + b^2 == c^2$)
    4. #
# # # # # When computing code complexity, we #
    #
  1. define the entire content of the innermost loop as an “atomic operation” which takes constant time.
    2. #
  2. describe the complexity as a function of $p$ (i.e., use $p$ as the “problem size” or “input size”). # Note, however, that the formal definition of “problem size” for a numeric input is the size it takes to represent the input, i.e. $n = \log(p)$. # Working with $p$ here is easier and more intuitive.
    3. #
# #### Trivial solution (v1): # # Go over all triplets of numbers in the relevant range, count only those where the above conditions hold. # # There are $p-1$ options for each variable $a,b,c$, so we need $(p-1)^3$ iterations and we can check each triplet in constant time. # # Complexity: $O(p^3)$ # In[1]: def num_of_triangles_v1(p): cnt = 0 for a in range(1, p): for b in range(1, p): for c in range(1, p): if a < b and a + b + c == p and a**2 + b**2 == c**2: cnt += 1 return cnt # #### Second version (v2): # # If we look at a pair of values for $a, b$, we can compute $c$ directly instead of going over all possible $c$ values in $\{1,2,\ldots,p-1\}$. # # We now use two nested loops instead of three (and omit the condition $a + b + c = p$). # # There are $(p-1)^2$ iterations, each one is again computed in constant time. # # Complexity: $O(p^2)$ # In[2]: def num_of_triangles_v2(p): cnt = 0 for a in range(1, p): for b in range(1, p): c = p - a - b if a < b and a**2 + b**2 == c**2 and c > 0: cnt += 1 return cnt # #### Third version (v3): # # Since we require $a < b$, in each iteration of the outer loop for $a$ we can define a lower bound for $b$, i.e. - in each iteration we need to check $b$ values between $a+1,\ldots, p-1$ instead of $1,\ldots,p-1$. # # The loops are now dependent and, therefore, to compute the number of atomic operations, we take a sum over $a$ of the number of $b$ values tested. # # In the $i$th iteration of $a$ (that is, for $a=i$) we need to check $p - 1 - i = p - (1 + i)$ values of $b$, so the total number of iterations is: $$\sum_{a = 1}^{p-1} (p - (1 + a)) = \sum_{i = 0}^{p-2} i = \frac{(p-1)(p-2)}{2} $$ # # Complexity: $O(p^2)$. # In[3]: def num_of_triangles_v3(p): cnt = 0 for a in range(1, p): for b in range(a + 1, p): c = p - a - b if a**2 + b**2 == c**2 and c > 0: cnt += 1 return cnt # #### Fourth version (v4): # # We now further improve our efficiency by defining **upper bounds** for $a,b$. we use the same strategy as in v3 to count operations. # # First of all, since $a < b < c$ and $a + b + c = p$, clearly $a < p/3$. That is, the maximal possible value of $a$ is $p//3$ (we will iterate till $p//3 + 1$ in order to include $p//3$ in the range). # # # Next, $b = p-a-c < p-a-b \implies 2b < (p-a)$. Thus: $b < (p-a)/2$. That is, the maximal possible value of $b$ is $(p-a)//2$ (again, we iterate till $(p-a)//2 + 1$ in order to include $(p-a)//2$ in the range). # # # The number of iterations is therefore: $$\sum_{a = 1}^{p/3} \left(\left\lfloor\frac{p-a}{2}\right\rfloor + 1 - (a+1)\right)\approx \sum_{a = 1}^{p/3} \frac{p}{2} - \frac{a}{2} - a =\frac{p^2}{6} - \frac{3}{2}\sum_{a = 1}^{p/3}a = \frac{p^2}{6} - \frac{3}{2}(p/3 + 1)\cdot \frac{p}{6} = \frac{p^2}{6} - \frac{p^2}{12} - \frac{p}{4} = \frac{p^2}{12} - \frac{p}{4}$$ # # # # # Complexity: $O(p^2)$. # In[4]: def num_of_triangles_v4(p): cnt = 0 for a in range(1, p//3 + 1): for b in range(a + 1, (p - a)//2 + 1): c = p - a - b if a**2 + b**2 == c**2: cnt += 1 return cnt # #### Fifth version (v5): # # We realize we have two equations in three variables, therefore there’s only a single free parameter here. # # $a+b+c=p \implies c = p-a-b$ # # Substitute $c$ with $p-a-b$ in $a^2+b^2=c^2$ to get $a^2 + b^2 = (p -a -b)^2$, open and isolate $b$ to get $b = \frac{p^2-2ap}{2(p-a)}$. # # So what do we need to do? We loop only over $a$, but need to make sure that the resulting $b$ is integral, and that $a < b$. Note that we do not have to calculate $c$ here # # # The number of iterations is $p/3$ and in each iteration we still do only a constant number of operations! # # Complexity: $O(p)$ # In[5]: def num_of_triangles_v5(p): cnt = 0 for a in range(1, p//3 + 1): b = (p**2 - 2*p*a)/(2*(p - a)) if int(b) == b and a < b: cnt += 1 return cnt # #### Experiment: # # We compare the change in running time of each of the functions as $p$ increases twofold. # # As expected, when $p$ increases by 2 and for large enough $p$ (so that asymptotic computations are valid): # # the cubical version ($O(p^3)$) runs in time which is roughly $2^3 = 8$ times longer, # # the quadratic versions ($O(p^2)$) runs in time which is roughly $2^2 = 4$ times longer, # # and the linear version ($O(p)$) runs in time which is roughly $2$ times longer. # # # In[8]: import time def elapsed(expression, number = 1): ''' computes elapsed time for executing code number of times (default is 1 time). expression should be a string representing a Python expression. ''' t1=time.perf_counter() for i in range(number): x = eval(expression) t2=time.perf_counter() return t2-t1 print("v1, p = 240 took",elapsed("num_of_triangles_v1(240)"), "secs") print("v2, p = 240 took",elapsed("num_of_triangles_v2(240)"), "secs") print("v3, p = 240 took",elapsed("num_of_triangles_v3(240)"), "secs") print("v4, p = 240 took",elapsed("num_of_triangles_v4(240)"), "secs") print("v5, p = 240 took",elapsed("num_of_triangles_v5(240)"), "secs") print("") print("v1, p = 480 took",elapsed("num_of_triangles_v1(480)"), "secs") print("v2, p = 480 took",elapsed("num_of_triangles_v2(480)"), "secs") print("v3, p = 480 took",elapsed("num_of_triangles_v3(480)"), "secs") print("v4, p = 480 took",elapsed("num_of_triangles_v4(480)"), "secs") print("v5, p = 480 took",elapsed("num_of_triangles_v5(480)"), "secs") print("") print("Since v5 is too fast for some machines to time, we check it for input size which is x100 and x200 bigger:") print("v5, p = 24000 took",elapsed("num_of_triangles_v5(24000)"), "secs") print("v5, p = 48000 took",elapsed("num_of_triangles_v5(48000)"), "secs") # # Big O notation # # 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)|$ # # # When $f,g$ are positive, an equivalent condition which is sometimes easier to check is that $$f(n) = O(g(n)) \iff \lim_{n \to \infty} \frac{f(n)}{g(n)} < \infty$$ # ### Time complexity hierarchy # # Let $n$ denote the size of the input and $c$ denote a constant. # The most common time complexities we encounter are : # # * Constant - $O(1)$ # * Logarithmic - $O(\log(n))$ # * Poly-logarithmic - $O(\log^c(n))$ for $c > 1$ # * Root/fractional - $O(n^{1/c})$ for $c>1$ # * Linear - $O(n)$ # * Loglinear - $O(n \log(n))$ # * Polynomial - $O(n^{c})$ for $c>1$ # * Exponential - $O(c^{n})$ for $c>1$ # # See also this list on [Wikipedia](http://en.wikipedia.org/wiki/Time_complexity#Table_of_common_time_complexities). # # # # ### $O(\cdot)$ - Facts # # Transitivity: # # * If $f(n) = O(g(n))$ and $g(n) = O(h(n))$ then $f(n) = O(h(n))$ # # Non-symmetry: # # * $f(n) = O(g(n))$ does not imply $g(n) = O(f(n))$ or $g(n) \neq O(f(n))$ # ### Prove or disprove # 1. $2^n = O(2^{n/2})$ # * Wrong, assume there exists $n_0, c>0$ such that for $n > n_0$ $2^n \leq c \cdot 2^{n/2}$. This implies $c \geq 2^{n/2} \to \infty$ as $n \to \infty$ in contradiction to $c$ being constant. # 2. $\log n! = O(n \cdot \log n)$ # * True. Note that as $\log(\cdot)$ is monotone increasing and that $\log (ab) = \log a + \log b$, thus: $\log n! = \log 1 + \ldots + \log n = \sum_{i=1}^n \log i \leq \sum_{i=1}^n \log n = n \cdot \log n$ # 3. If $f_1(n) = O(g_1(n)), f_2(n) = O(g_2(n))$ then $f_1(n) + f_2(n) = O(g_1(n)+g_2(n)) = O(\max \{g_1(n),g_2(n)\})$ # * True. Let $n_1, c_1$ and $n_2, c_2$ be the constants such that $n > n_1 \implies f_1(n) \leq c_1 g_1(n)$ and $n > n_2 \implies f_2(n) \leq c_2 g_2(n)$ and note that for $n_3 = n_1 + n_2$ we have that if $n > n_3$: $$f_1(n) + f_2(n) \leq c_1 g_1(n) + c_2 g_2(n) \leq (c_1 + c_2) (g_1(n) + g_2(n)) \leq 2 (c_1 + c_2) \max\{g_1(n),g_2(n)\}$$ Thus the first claim holds with constants $n_3, (c_1 + c_2)$ and the second with $n_3, 2(c_1 + c_2)$ # * The above is also true for any $k$ functions $f_1, \ldots, f_k$ where $k$ is a constant. A direct consequence of which is: # 4. For any constant $k \geq 1$ and constants $a_0, \ldots, a_k \in \mathbb{R}$: $$f(n) = a_0 \cdot n^0 + a_1 \cdot n^1 + \cdots + a_k\cdot n^k = O(n^k)$$ # * True. Let $a_\max = \max\{|a_0|,\ldots,|a_k|\}$ and observe that $f(n) \leq a_\max n^0 + a_\max n^1 + \cdots + a_\max n^k = k a_\max n^k$. The claim follows as $k a_\max$ is a constant # 5. For any constant $k > 1$: $\log_2^k n = O\left(\log_{10}^k n\right)$ # * True. Basic logarithm identities show us that $\log_2^k n = \left(\frac{\log_{10} n}{ \log_{10} 2}\right)^k = \left(\frac{1}{ \log_{10} 2}\right)^k \cdot \log_{10}^k n$. The claim follows as $\left(\frac{1}{ \log_{10} 2}\right)^k$ is a constant. # * Letting $k = 1$ we can generalize the above: for any constants $a,b$ we have both $\log_a n = O(\log_b n)$ and $\log_b n = O(\log_a n)$. Because of this, we usually omit the base of the logarithm when using $O(\cdot)$ notation (if it is constant!) and simply say $O(\log n)$ # # # ### If time permits # 1. For any two functions $f,g$, $f(n) = O(g(n)) \implies 2^{f(n)} = O(2^{g(n)})$ # * Wrong. Letting $f(n) = n, g(n) = n/2$ this is the first example from the previous section. # 2. $\sum_{i = 0}^{\log n}\frac{i}{2^n} = O(1)$ # * True. We first see that $\sum_{i = 0}^{\log n}\frac{i}{2^n} \leq \frac{\log^2 n}{2^n} = \frac{2^{\log \log^2 n}}{2^n} =\frac{2^{2\log \log n}}{2^n}$ The claim follows by noting that for large enough $n$ we have: $n > \log \log n$) # # In[ ]: