## Issue

So I recently started my studies on data structures and algorithms, specifically big O notation. I get the basics so far. As an exercise I wanted to determine the time complexity of an algorithm I wrote not too long ago.

My program uses PIL or pillow to make a contact sheet. Basically a collage of `self.imageCount`

amount of images. I spent allot of time thinking on how to efficiently calculate the size that each image has to be in order to fit all of them on the sheet.

Finally I came up with this

I’ll let the function speak for itself.

```
def calc_size(self):
"""
Calculates size of each image by stating with a maximum height, then slowly
decreasing it until enough rows and columns can be formed to fit all images.
"""
self.imageHeight = self.sheetHeight
self.imageWidth = self.imageHeight * (2/3) # The aspect ratio is located here
self.rows, self.cols = 1, 1
while self.rows * self.cols < self.imageCount:
self.imageHeight -= 1
self.imageWidth = int(self.imageHeight * (2/3))
self.rows = self.calc_rows()
self.cols = self.calc_cols()
"""
The two functions below simply prevent zero division later in the program
when I calculate the gap between each image
"""
def calc_rows(self):
if int(self.sheetHeight/self.imageHeight) == 0:
return 1
return int(self.sheetHeight/self.imageHeight)
def calc_cols(self):
if int(self.sheetWidth/self.imageWidth) == 0:
return 2
return int(self.sheetWidth/self.imageWidth)
```

So my question is, what is the time complexity of `calc_size`

? I’ve run some tests where I pushed `self.imageCount`

up to 10 000 and the runtime never really exceeded 0.004 seconds. This makes me think that it’s O(log n). But why…I don’t know.

## Solution

Assuming, the aspect ratio of the sheet and the aspect ratio of the images are equal, the answer would be O(`sheetHeight`

).

Let’s consider the worst-case scenario. Let’s assume for a moment that `imageCount`

is very large, so much so that an image would have to shrink down to one pixel. Then, the number of times the while loop is executed would be equal to `self.sheetHeight - 1`

. Therefore, the function would be O(`sheetHeight`

).

It seems like in your case the aspect ratios are equal, but assuming they are not equal, then the answer is one of O(`sheetHeight`

) or O(`sheetWidth`

). Say for example the image width is 1/2 image height. Since 2/3 > 1/2, the limiting direction is the height (the height would hit the limit first). Then the answer would be O(`sheetHeight`

).

**Edit:** For a Big O in terms of `imageCount`

, consider the following:

For simplicity, I’ll assume the aspect ratios of the sheet and image are the same.

Let’s take `imageHeight`

to be the required height of the image. Say `imageCount = 100`

. Then `imageHeight=sheetHeight/10`

.

Now, say we multiply `imageCount`

by 4. Now the `imageHeight`

would have to be `sheetHeight/20`

. Thus, we can see that the image height is proportional to `1/sqrt(imageCount)`

.

But, the time complexity is actually dependent on `sheetHeight - imageHeight`

since that’s the number of times the while loop would be executed. Thus, we can say that the solution is O(`sheetHeight - imageHeight`

) = O(`sheetHeight - sheetHeight/sqrt(imageCount)`

) = O(`1 - 1/sqrt(imageCount)`

) (assuming `sheetHeight`

is constant).

So, if we take `n = imageCount`

, the solution is O(`1-1/sqrt(n)`

). This explains why for large imageCounts, the solution approaches a constant time consumption.

Answered By – Dilith Jayakody

Answer Checked By – Pedro (BugsFixing Volunteer)