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.
Assuming, the aspect ratio of the sheet and the aspect ratio of the images are equal, the answer would be O(
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(
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(
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.
imageHeight to be the required height of the image. Say
imageCount = 100. Then
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
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)