cs1001.py , Tel Aviv University, Spring 2020

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(\cdot)$.

Takeaways:

  • Analyzing the running time complexity of a function can teach us about how the running time would change as a function of the input size
  • Two functions that have the same running time complexity may differ in their running time (one can be more efficient than the other)
  • Big $O(\cdot)$ notation effectively "hides" additive and multiplicative constants
  • When analyzing a nested loop, we can sum over the boundaries of the external loop, when each summand will be the number of iterations of the inner loop within a given iteration of the external loop

Problem:

Given a natural number $p$, how many right triangles exist with integer-sized sides whose perimeter is $p$?

Formally:

Given a natural number $p > 0$, how many triplets $(a,b,c)$ are there such that:

  1. $a^2 +b^2 == c^2$
  2. $a + b + c == p$
  3. $a,b,c > 0$ are all integers
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. The case $a = b$ cannot hold as this would imply $2a^2 = c^2 \implies c = \sqrt{2} a$
  3. The condition $b < c$ is redundant (since we require that $a,b,c > 0$ and $a^2 + b^2 == c^2$)

When computing code complexity, we

  1. define the entire content of the innermost loop as an “atomic operation” which takes constant time.
  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.

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\approx p^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\approx p^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")
v1, p = 240 took 2.0098203190000277 secs
v2, p = 240 took 0.07364331099995525 secs
v3, p = 240 took 0.055745446999935666 secs
v4, p = 240 took 0.013294021999968209 secs
v5, p = 240 took 0.00012039499995353253 secs

v1, p = 480 took 17.873038491999978 secs
v2, p = 480 took 0.337060590999954 secs
v3, p = 480 took 0.3156459970000469 secs
v4, p = 480 took 0.044534067999961735 secs
v5, p = 480 took 0.00019973799999206676 secs

Since v5 is too fast for some machines to time, we check it for input size which is x100 and x200 bigger:
v5, p = 24000 took 0.01722720300006131 secs
v5, p = 48000 took 0.03454993299999387 secs

Big O notation

Given two functions $f(n)$ and $g(n)$, we say that: $$f(n) = O(g(n))$$ And we sometimes ommit the indeterminate and simply sat that: $$f = O(g)$$ If there exists a constant $c > 0$ and $n_{0}\in \mathbb{N}$ 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 > 1$ denote a constant. Here are some common classes of functions we encounter:

  • Constant - $O(1)$
  • Logarithmic - $O(\log(n))$
  • Poly-logarithmic - $O(\log^c(n))$
  • Root/fractional - $O(n^{1/c})$
  • Linear - $O(n)$
  • Loglinear - $O(n \log(n))$
  • Polynomial - $O(n^{c})$
  • Exponential - $O(c^{n})$

See also this list on Wikipedia.

$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 \leq 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 [ ]: