2

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?

Improve this question
5
  • 3
    usually constants are excluded from time complexity, and in the first example, tbere are always only 4 loop iterations so O(4) is O(1), and for the second example, if N is defined as the number of values, it is indeed O(N) since it only iterates through each value once, so maybe you should be clearer about what N is? for the second case, it could also be O(NM) where N is rows and M is columns Commented Aug 18, 2020 at 15:22
  • @mattyx17, but total_columns is explicitly provided as a parameter to the function, and is thus not a constant. The second function is definitely O(n*m) where n and m are the number of rows and columns respectively. Commented Aug 18, 2020 at 15:26
  • Perhaps someone coming from a data analysis field would expect total_columns to be "small", because they are typically a handful of "named" variables. However, there is nothing in the problem to suggest that values isn't some arbitrary matrix, and someone coming from, say, an image processing background would absolutely consider total_columns to be an arbitrary variable. Commented Aug 18, 2020 at 15:28
  • 1
    Or perhaps n is defined as the number of values in the values matrix. Then it is indeed O(n). Commented Aug 18, 2020 at 15:43
  • @TheRealOrange N is not specified anywhere, the complete question is as I wrote it. Thank you for explaining the O(1) I get it now, a silly mistake on my end. Commented Aug 18, 2020 at 16:57

2 Answers 2

Reset to default
1

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

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

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.

Improve this answer

2 Comments

even if the first question used any data structure other than set, the complexity would have been O(1) as the size is constant and doesn't vary as per user input.
The answer to the first exercise is O(1) because the set colours has a constant size, regardless of any input (which the function doesn't accept anyway). Because of this, the foreach loop always performs 4 iterations.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.