Algorithm is linear (O(n)) to size of input, but what if input size is exponential

Question

The instructor said that the complexity of an algorithm is typically measured with respect to its input size.

So, when we say an algorithm is linear, then even if you give it an input size of 2^n (say 2^n being the number of nodes in a binary tree), the algorithm is still linear to the input size?

The above seems to be what the instructor means, but I’m having a hard time turning it in my head. If you give it a 2^n input, which is exponential to some parameter ‘n’, but then call this input “x”, then, sure, your algorithm is linear to x. But deep-down, isn’t it still exponential in ‘n’? What’s the point of saying its linear to x?

Answer 1

Whenever you see the term "linear," you should ask - linear in what? Usually, when we talk about an algorithm's runtime being "linear time," we mean "the algorithm's runtime is O(n), where n is the size of the input."

You're asking what happens if, say, n = 2^k and we're passing in an exponentially-sized input into the function. In that case, since the runtime is O(n) and n = 2^k, then the overall runtime would be O(2^k). There's no contradiction here between this statement and the fact that the algorithm runs in linear time, since "linear time" means "linear as a function of the size of the input."

Notice that I'm explicitly choosing to use a different variable k in the expression 2^k to call attention to the fact that there are indeed two different quantities here - the size of the input as a function of k (which is 2^k) and the variable n representing the size of the input to the function more generally. You sometimes see this combined, as in "if the runtime of the algorithm is O(n), then running the algorithm on an input of size 2ⁿ takes time O(2ⁿ)." That statement is true but a bit tricky to parse, since n is playing two different roles there.