1

Assume you had a data set of size n and two algorithms that processed that data set in the same way. Algorithm A took 10 steps to process each item in the data set. Algorithm B processed each item in 100 steps. What would the complexity be of these two algorithms?

I have drawn from the question that algorithm A completes the processing of each item with 1/10th the complexity of algorithm B,and using the graph provided in the accepted answer from the question: What is a plain English explanation of "Big O" notation? I am concluding that algorithm B has a complexity of O(n^2) and algorithm A a complexity of O(n), but am struggling to make conclusions beyond that without the implementation.

Community
  • 1
  • 1
  • 1
    Using only a single benchmark of 10 steps for A and 100 steps for B, we cannot conclude the complexity. However, if, for example, you had another point of 25 steps for A and 625 steps for B, then it might support your conclusion. – Tim Biegeleisen Sep 07 '16 at 01:14

1 Answers1

4

You need more than one data point before you can start making any conclusions about time complexity. The difference of 10 steps and 100 steps between Algorithm A and Algorithm B could be for many different reasons:

  1. Additive Constant difference: Algorithm A is always 90 steps faster than Algorithm B no matter the input. In this case, both algorithms would have the same time complexity.

  2. Scalar Multiplicative difference: Algorithm A is always 10 times faster than Algorithm B no matter the input. In this case, both algorithms would have the same time complexity.

  3. The case that you brought up, where B is O(n^2) and A is O(n)

  4. Many, many other possibilities.

adao7000
  • 3,632
  • 2
  • 28
  • 37