1
$\begingroup$

What is actually meant when we say 'size/length of an input'? As far as I have interpreted it in different books,it means the values of the parameters to be inputted in an algorithm. But I am actually confused of what it really is. And further they state that time complexity of algorithms is usually a function of the size of the input. For instance,if I take the problem of multiplication of square matrix of order $p$ by itself, then is $p$ the size of the input? If so then,the time complexity does depend on it. Is my interpretation correct?

$\endgroup$
1
  • 1
    $\begingroup$ Input length depends on how the input is stored, too. For example, the arrays [6], [], [1,8,3] have 1, 0, 3 values respectively. Mapping a function across these arrays depends on the number of values: 1, 0, 3 times respectively. So in this example, input length is the number of values. But what if we define a OneTo(n) iterator that starts counting at 1 and ends at n? We only need to store the counter and n, which is 2 values. But if we map a function over this, we would still need to call the function n times. So in that example, the input length is the value n. $\endgroup$
    – BatWannaBe
    Aug 25 '21 at 18:47
1
$\begingroup$

The input size, is roughly measured by "how many values do we store here?", and if you want to be more specific, you will also include "how much data (in terms of bits) do the values take?".

In the matrix case, if the matrix is of order $p\times p$, then it has $p^2$ elements in it. Hence, its "size" will be said to be $O(p^2)$.

When talking in formal terms for turing machines, the input is simply a string. This string can encode matrices, or anything else you want - but it still will always be a string. Think of how you write a vector: as a combination of letters, brackets and numbers - its a string! Strings are nice: the input size is defined to be the number of "letters" in the string. For example, the binary string "1101" will have size $4$, while the binary string "010101" will have size $6$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.