2
$\begingroup$

Given this algorithm:

int foo(int num) {
    if (num == 0){
        return 0;
    } else {
        return 1 + foo(num/10);
    }
}

Me and my friend are debating how you should treat "N" as the size of the input.

If I'm considering N to be the number of digits: then my analysis will say O(n)

However, if I'm considering N to be the actual value of the input to the function I will get a different runtime representation and different analysis with the conclusion of O(log n) (base 10)

Me and my friend cannot understand why the second approach is wrong, so far we got explanations like : "The algorithm is cutting the number digit by digit so your N is the number of decimal digits of the number"

However, log (base 10) of the actual value will give me pretty much the same result.

Why is the second approach is wrong ?

Improve this question
$\endgroup$
2
  • $\begingroup$ Note that $O(\log n)$ doesn't depend on the base of the logarithm. $\endgroup$ Commented Jan 3, 2017 at 20:37
  • $\begingroup$ It's not wrong: different models lead to different answers. $\endgroup$ Commented Jan 3, 2017 at 22:37

2 Answers 2

Reset to default
2
$\begingroup$

There is nothing inherently wrong about either approach, however the first one is overwhelmingly more common. The reason is that complexity analysis takes place in an asymptotic setting with respect to the size of input.

Computers are machines that perform meaningless operations on meaningless symbols, it is your job to find meaning in the computation. Therefore, determining what the size is depends on some agreed upon definition of what constitutes a reasonable symbolic representation of the input. Formally, you would have to define how the machine that executes your algorithm works in order to be able to talk about complexity at all, but in this context it is sufficient to assume that any representation that uses a finite set of symbols is acceptable.

There are many ways - all in principle equally valid - to represent the natural numbers. For instance, you might say that $0$ is represented by the string x, $1$ by xx, $2$ by xxx and so on. In this case the size of input would be proportional to the numerical value.

However most of us would agree that representing numbers in some base $b$ - which is certainly acceptable as it requires at most $b$ symbols - is more reasonable; in this case the size of the input is proportional to the number of digits required to write the representation of the number, which is itself proportional to the logarithm of the numerical value.

Taking numbers to have size proportional to their logarithm is also more consistent with the way we treat other objects. If the input of an algorithm is an array, the size of the array is the number of cells (and not the number of different arrays of that length), similarly for graphs, matrices and other mathematical objects.

Improve this answer
$\endgroup$
1
$\begingroup$

When encoded in base $b$, the input $n$ has size roughly $\log_b n$. Sometimes we instead encode whole numbers in unary: the number $n$ is encoded as $n$ times some fixed character. Under that encoding, the input $n$ has size $n$.

How you encode the input depends on you, though usually a base $b$ encoding is used. In particular, the model we use for analyzing algorithms (the random access machine) implicitly assumes that the inputs are encoded in base $b$. Therefore your first running time is the correct one, and the other one is wrong.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.