# [SOLVED] What is the time complexity of this function which calculates the size of an image on a contact sheet?

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