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. Two solutions that have the same time complexity bound may differ in their running time (one can be more efficient than the other).
  3. The Big O notation "hides" additive and multiplicative constants
  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. 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.


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. $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$ 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")
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)$,

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

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