for row in range(0, height, 2):
for col in range(0, width, 2):
# Each pixel in the result image use the the average
# colour of the 2x2 pixels from the original image
# (i.e. the pixel itself in row,col and pixels in
# row,col+1 -- row+1,col -- row+1, col+1
sumR = 0
sumG = 0
sumB = 0
for r in range(row, row+2): # r will be row and row+1
for c in range(col, col+2): # c will be col and col+1
sumR += img[r][c][0]
sumG += img[r][c][1]
sumB += img[r][c][2]
Would the time complexity for this algorithm be O(height * width)?
1
Yes, it will be O(height * width).
for row in range(0, height, 2):
for col in range(0, width, 2):
This will execute height/2 * width / 2 iterations. Throw out the constants and it’s O(height * width).
for r in range(row, row+2): # r will be row and row+1
for c in range(col, col+2): # c will be col and col+1
This will execute 2 * 2 = 4 iterations. That’s a constant and it’s ignored.
All other operations are constant time and ignored.
Always try to break these types of questions down into small parts:
Starting with the OuterLoops:
The outer loop (row) iterates from 0 to height in steps of 2, so the runtime will be approximately Height/2 times
The inner loop (col) iterates from 0 to width in steps of 2 as well, so similarly, the runtime will be approximately width/2 times.
This gives you a runtime for the OuterLoops to be approximately:
height/2 * width/2
Now, if we look at the InnerLoops:
For each iteration run by the outer loops, the nested inner loops(R & C) run over a 2*2 block (which is four iterations)
Then, this will be a constant that adds to each iteration.
Thus, it will be something like this:
(height/2) * (width/2) * 4 == height * width
But in asymptotic complexity, we ignore the constant factor,
This means we can go from the above equation into this straight away:
height * width