Calculating Time Complexity of an Algorithm

user_10628620 0
Viewed 261

I am learning about calculating the time complexity of an algorithm, and there are two examples that I can't get my head around why their time complexity is different than I calculated.

After doing the reading I learned that the for-loop with counter increasing once each iteration has the time complexity of O(n) and the nested for-loop with different iteration conditions is O(n*m).

This is the first question where I provided the time complexity to be O(n) but the solution says it was O(1):

function PrintColours():
    colours = { "Red", "Green", "Blue", "Grey" }

    foreach colour in colours:
       print(colour)

This is the second one where I provided the time complexity to be O(n^2) but the solution says its O(n):

function CalculateAverageFromTable(values, total_rows, total_columns):
     sum = 0
     n = 0
     for y from 0 to total_rows:
          for x from 0 to total_columns:
              sum += values[y][x]
              n += 1

     return sum / n

What am I getting wrong with these two questions?

time-complexity algorithm
2 Answers

There are several ways for denoting the runtime of an algorithm. One of most used notation is the Big - O notation. Link to Wikipedia: https://en.wikipedia.org/wiki/Big_O_notation

big O notation is used to classify algorithms according to how their run time or space requirements grow as the input size grows.

Now, while the mathematical definition of the notation might be daunting, you can think of it as a polynomial function of input size where you strip away all the constants and lower degree polynomials.

For ex: ax^2 + bx + c in Big-O would be O(x^2) (we stripped away all the constants a,b and c and lower degree polynomial bx)

Now, let's consider your examples. But before doing so, let's assume each operation takes a constant time c.

First example:

Input is: colours = { "Red", "Green", "Blue", "Grey" } and you are looping through these elements in your for loop. As the input size is four, the runtime would be 4 * c. It's constant runtime and constant runtime is written as O(1) in Big-O

Second example:

The inner for loop runs for total_columns times and it has two operations

for x from 0 to total_columns:
  sum += values[y][x]
  n += 1

So, it'll take 2c * total_columns times. And, the outer for loop runs for total_rows times, resulting in total time of total_rows * (2c * total_columns) = 2c * total_rows * total_columns. In Big-O it'd be written as O(total_rows * total_columns) (we stripped away the constant)

When you get out of outer loop, n which was set to 0 initially, would become total_rows * total_columns and that's why they mentioned the answer to be O(n).

user_55047580

One good definition of time complexity is:

"It is the number of operations an algorithm performs to complete its task with respect to the input size".

If we think the following question input size can be defined as X= total_rows*total_columns. Then, what is the number of operations? It is X again because there will be X addition because of the operation sum += values[y][x] (neglect increment operation for n += 1 for simplicity). Then, think that we double array size from X to 2*X. How many operations there will be? It is 2*X again. As you can see, increase in number of operations is linear when we increase input size which makes time complexity O(N).

function CalculateAverageFromTable(values, total_rows, total_columns):
 sum = 0
 n = 0
 for y from 0 to total_rows:
      for x from 0 to total_columns:
          sum += values[y][x]
          n += 1

 return sum / n

For your first question, the reason is that colours is a set. In python, {} defines a set. Accessing elements from unordered set is O(1) time complexity regardless of the input size. For furher information you can check here.

user_187066340
Related