How is 'n' always the 'input size' in O(n)?

Question

Consider the following code:

void counterMethod(int n)
{
    int count=0;
    for(int i=0; i<n; i++)
    {
    count++;
    }

}

Since the time complexity of this function would be O(n), but here 'n' refers to the 'value of input' not the 'size of input'. Please clarify why is it 'input size' according to the formal definition:

"Time complexity is the amount of time taken by an algorithm to run, as a function of the length of the input"

Does this answer your question? [What is a plain English explanation of "Big O" notation?](https://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation) — shree.pat18, Jun 06 '21 at 08:02
The formal definition that you quote uses the word 'length'. In the case of an integer input value and size seem synonymous and length can be taken to mean the same thing too. — Ross Attrill, Jun 06 '21 at 08:07
I am just saying that length, size and value are different words / synonyms for the same thing in case of the integer n — Ross Attrill, Jun 07 '21 at 04:40

score 1 · Answer 1 · answered Jun 06 '21 at 10:20

In edge-cases like this, the formal definition of "input size" which theorists use does not agree with the practical definition which most programmers use when thinking about actual code.

The formal definition of "input size" is the number of bits (or sometimes machine words) required to represent the input. In most cases this is proportional to e.g. the length of an array, the size of a dictionary, or so on, so the definition is equivalent. Formally, your counting method's time complexity is O(2^N) where N is the number of bits required to represent the input number. (Usually you would write lowercase n for the number of bits and uppercase N for the actual numerical value, for readability; uppercase N is "bigger".) The formal definition is like this so that terms like "polynomial time" and "NP" have exact meanings which make sense for a variety of different algorithm inputs.

The intuitive, practical definition is that you can measure "input size" by any variable or quantity that matters for your application. Often, the numerical value of an integer is more important to your application than the number of bits required to represent it; typically you don't care about the number of bits. In that case your counting method takes O(n) time where n is the value of the integer.

Most programmers (e.g. on Stack Overflow) will talk about time complexity using this practical definition, simply because it's easier and more useful for real programming. So in your case, O(n) isn't a time complexity according to the formal definition, but if the reason you want to know the time complexity is because you want to estimate how long the code will take to run, or compare it with another algorithm to see which should be faster, then you won't care about the formal definition.

How is 'n' always the 'input size' in O(n)?

1 Answers1