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

Answered By – Dilith Jayakody

Answer Checked By – Pedro (BugsFixing Volunteer)

Leave a Reply

Your email address will not be published. Required fields are marked *