ROUGH DRAFT authorea.com/5734
Main Data History
Export
Show Index Toggle 0 comments
  •  Quick Edit
  • Algorithms - Lab 1, Problem 2

    Introduction

    This is a hand-in written by Group 7 (FIRE) for the Algorithms course (TIN092) at Chalmers University of Technology.

    Group 7 consists of:

    • Mazdak Farrokhzad

      • 901011-0279

      • twingoow@gmail.com

      • Program: IT

    • Niclas Alexandersson

      • 920203-0111

      • nicale@student.chalmers.se

      • Program: IT

    This problem deals with complexity analysis of a recursive algorithm to rotate the pixels of a bitmap. The algorithm uses a low level operation called a blit, which copies one rectangular chunk of pixels from one location to another. The algorithm works by splitting the bitmap into four sections of equal size, using a sequence of five blits to move the sections into their right place, then recursively rotating each section in the same manner.

    function rotate(s) begin if side length of s > 1 then split s into 4 sections blit sections into place for each section loop rotate(section) end loop end if end

    Laws and forumulas of summation

    These summation laws/formulas are used. They are very common and thus we won’t prove any of them. Most of them can be found here.

    1. \(\displaystyle\sum_{n=s}^t C\cdot f(n) = C\cdot \sum_{n=s}^t f(n)\)

    2. \(\displaystyle\sum_{i = 0}^{n-1} a^i = \frac{1 - a^n}{1 - a}\)

    a) Number of blits

    The number of blit operations can be expressed as: \[T(n) = \begin{cases} 0, & n=1\\ 5 + 4 T(\frac{n}{2}), & n > 1 \end{cases}\]

    For \(n = 2^x\) we try the algorithm for incremental sizes of \(x\) to find a pattern for how the algorithm behaves.

    \[\begin{aligned} T(2^0) &= 0\\ T(2^1) &= 5\\ T(2^2) &= 5 + 5 \cdot 2^2\\ T(2^3) &= 5 + 5 \cdot 2^2 + 5 \cdot 2^4\\ T(2^4) &= 5 + 5 \cdot 2^2 + 5 \cdot 2^4 + 5 \cdot 2^6\\ T(2^5) &= 5 + 5 \cdot 2^2 + 5 \cdot 2^4 + 5 \cdot 2^6 + 5 \cdot 2^8\end{aligned}\]

    We hypothesise that: \[\begin{split} T(2^n) &= \sum_{i = 0}^{n-1} \left[5 \cdot 4^i\right] = 5\sum_{i = 0}^{n-1} \left[4^i\right]\\ &= 5\frac{1 - 4^n}{1 - 4} = \frac{5 - 5 \cdot 4^n}{-3}\\ &= \frac{5 \cdot 4^n - 5}{3} \end{split}\]

    Proof by induction:
    This holds for the base cases \(n \in \{0, 1, 2, 3, 4\}\) (verifying this is left as an exercise for the reader).

    Now we show that the above expression is true for all \(n \geq 0\). Given that \(T(2^n) = \frac{5 \cdot 4^n - 5}{3}\) is true for some \(n\), we need to show that \(T(2^{n+1}) = \frac{5 \cdot 4^{n+1} - 5}{3}\). Using the above definition of \(T(n)\), we get: \[\begin{split} T(2^{n+1}) &= 5 + 4\frac{5 \cdot 4^n - 5}{3}\\ &= 5 + \frac{5 \cdot 4^{n+1} - 5 \cdot 4}{3}\\ &= \frac{5 \cdot 4^{n+1} + 5 \cdot 3 - 5 \cdot 4}{3}\\ &= \frac{5 \cdot 4^{n+1} - 5}{3} \end{split}\] Q.E.D.

    This gives us that: \[\begin{split} T(n) &= \frac{5 \cdot 4^{\log(n)} - 5}{3}\\ &= \frac{5(2^2)^{\log(n)} - 5}{3}\\ &= \frac{5n^2 - 5}{3}\\ T(n) &\in \mathcal{O}(n^2) \end{split}\]

    b) Complexity

    We are given that the runtime complexity of a single blit operation for a section of dimentions \(n\cdot n\), is \(\mathcal{O}(n^2)\).

    Given this information, the runtime complexity of the rotation algorithm can be expressed as: \[T(n) = \begin{cases} 0, & n=1\\ 5 \cdot (\frac{n}{2})^2 + 4 T(\frac{n}{2}), & n > 1 \end{cases}\]

    Once again, we use \(n=2^x\) for increasing values of \(x\) and try to find a pattern.

    \[\begin{aligned} T(2^0) &= T(1) = 0\\ T(2^1) &= 5 \cdot (2^0)^2 + 4 T(2^0) = 5 + 0 = 5\\ T(2^2) &= 5 \cdot (2^1)^2 + 4 T(2^1)\\ &= 5 \cdot 4^1 + 4 \cdot 5 = 2(5 \cdot 4)\\ T(2^3) &= 5 \cdot (2^2)^2 + 4 T(2^2)\\ &= 5 \cdot 4^2 + 4(2(5 \cdot 4^1))\\ &= 5 \cdot 4^2 + 2(5 \cdot 4^2) = 3(5 \cdot 4^2)\\ T(2^4) &= 5 \cdot (2^3)^2 + 4 T(2^3)\\ &= 5 \cdot 4^3 + 4(3(5 \cdot 4^2))\\ &= 5 \cdot 4^3 + 3(5 \cdot 4^3) = 4(5 \cdot 4^3)\\ T(2^5) &= 5 \cdot (2^4)^2 + 4 T(2^4)\\ &= 5 \cdot 4^4 + 4(4(5 \cdot 4^3))\\ &= 5 \cdot 4^4 + 4(5 \cdot 4^4) = 5(5 \cdot 4^4)\\\end{aligned}\]