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
```

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.

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

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

## Share on Social Media