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