How do we define a "step" when calculating big O notation in an algorithm?

Question

I'm learning about Big O notation and how it relates to computer science and I understand the sentiment behind Big O, however I'm struggling at understanding how we define a "step".

In the book I'm reading as well as a lot of different articles they use something like below to express an O(N) example since, as N increases we perform more steps linearly:

void printAllElementOfArray(int arr[], int size)
{
    for (int i = 0; i < size; i++)
    {
        printf("%d\n", arr[i]);
    }
}

I understand the purpose of the example wherein for the function above "we perform printf N times" and therefore the algorithm is best represented through f(N) <= O(N) (I think that's the mathematical meaning, I get the sentiment of Big O but not fully there yet on the math).

The piece I'm really struggling with though is why we consider "printf" a single step. printf is in itself its own function with its own sequence of steps and so to that end, does that function not need to be elaborated? Is there any defined criteria of when an inner function is elaborated vs when we define it as a unit step?

I read somewhere that usually for nested functions big O is the multiplication of steps for each function O(g(N) x f(N)).

• So to that end, is the implication/assumption here that printf is O(1) and therefore the overall algorithm is O(1*N)?

Any clarifications is really appreciated.

Answer 1

A step is anything that takes time, memory, or whatever you are measuring behind the label of "complexity". A step can be any size, as long as it is roughly the same size each time it gets done, so that you can reasonably say "doing this twice takes twice as much <x> as doing it once".

is the implication/assumption here that printf is O(1)

Yes.

If printf performance scales with some part of the input (for example, the size of the numbers being printed), you might call that "M" and say that the complexity is O(N*M) or O(N*log(M)). But if the scaling you are interested in is "amount of numbers" rather than "size of numbers", you can treat that as a constant factor. You'll find that this is unfortunately done quite often without explicitly stating it.

Answer 2

is the implication/assumption here that printf is O(1) and therefore the overall algorithm is O(1*N)?

This. I'd say the example you've quoted (which I appreciate you've just taken from somewhere else) isn't a great example precisely because of the uncertainty about this assumption. Perhaps a better example would be something like

int sumArray(int arr[], int size)
{
    int sum = 0;
    for (int i = 0; i < size; i++)
    {
        sum += arr[i];
    }
    return sum;
}

as we're now dealing with a much simpler operation. Ideally, any explanation makes these kind of assumptions clear.

Answer 3

You are correct that we need to consider the big-O of printf as well and the teaching material that you got your example from is taking a big shortcut by ignoring that.

Now, looking at printf, a single call to that function is not going to do a different amount of work if you change the size of your array. By that reasoning, printf is O(1) with regard to the part of your algorithm you are interested in. (It might have a different big-O if you, for example, consider the values within the array.)

I read somewhere that usually for nested functions big O is the multiplication of steps for each function O(g(N) x f(N)).

• So to that end, is the implication/assumption here that printf is O(1) and therefore the overall algorithm is O(1*N)?

Yes, that is completely correct.

I'm struggling at understanding how we define a "step".

It might not be the formal definition, but the easiest way is to consider as a "step" every operation and function call where you know that the amount of work and memory doesn't change when your input size changes..

In other words, a "step" is every operation in your algorithm that you know to be O(1).

Answer 4

Is there any defined criteria of when an inner function is elaborated vs when we define it as a unit step?

When it depends on N.

So to that end, is the implication/assumption here that printf is O(1) and therefore the overall algorithm is O(1*N)?

Yes, printf doesn't depend on N, so it's O(1), and the N dominates.

Is there any defined criteria of when an inner function is elaborated vs when we define it as a unit step?

One way of looking at it is to just plot the time taken against values of N and see if it looks linear, logarithmic, or whatever. That should help your intuition of which terms are dominating.

Note that this is the asymptotic complexity: it gives the shape of the curve as N shoots off towards infinity.

Let's compare two printf implementations:

• printf_slow takes a million years to complete and uses a petabyte of working memory, but it is a fixed million years and a fixed petabyte and neither depends on N

• printf_fast takes log(N) nanoseconds and uses no storage at all

  (it's actually not implausible for printf to take log(N) time, since that's how many digits it needs to format)

Now the first version is constant time and the overall function is linear O(N), but takes about N million years per run.

The second version is logarithmic time and the overall function is O(N log N), which looks asymptotically worse, even though int size cannot store a large enough value for N that the second function will ever take longer to execute.

If we allow N to really shoot off towards infinity (ie, increase without bound assuming no storage constraints for size itself), then the second version will eventually take longer than the first - I think when size is around 10 to the power of 31 sextillion.