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.

Answer 2

Lets say you are printing first n numbers, and to print each number it takes 3 operations:

n-> 10, number of operations -> 3 x 10 = 30

n-> 100, number of operations -> 3 x 100 = 300

n-> 1000, number of operations -> 3 x 1000 = 3000

n ->10000, we can also say, n = 100^2 (say k^2), number of operations --> 3 x 10000 = 30,000 Even though n is exponent of something(in this case 100), our number of operations solely depends upon number on the input(n which is 10,000).

So we can say, it is linear time complexity algorithm.

Answer 3

When we say an algorithm is O(n), means if the input size is n, it is linear regards to the input size. Hence, if n is exponential in terms of another parameter k (for example n = 2^k), the algorithm is linear as well, in regards to the input size.

Another example is time complexity for the binary search for an input array with size n. We say that binary search for a sorted array with size n is in O(log(n)). It means in regards to the input size, it takes asymptotically at most log(n) comparison to search an item inside an input array with size n,

Answer 4

If an algorithm has a linear time-complexity, then it is linear regardless the size of the input. Whether it is a fixed size input, quadratic or exponential.

Obviously running that algorithm on a fixed size array, quadratic or exponential will take different time, but still, the complexity is O(n).

---

Perhaps this example will help you understand, does running merge-sort on an array of size 16 mean merge-sort is O(1) because it took constant operations to sort that array? the answer is NO.