Precise Input Size and Time Complexity

Question

When talking about time complexity we usually use n as input, which is not a precise measure of the actual input size. I am having trouble showing that, when using specific size for input (s) an algorithm remains in the same complexity class.

For instance, take a simple Sequential Search algorithm. In its worst case it takes W(n) time. If we apply specific input size (in base 2), the order should be W(lg L), where L is the largest integer.

How do I show that Sequential Search, or any algorithm, remains the same complexity class, in this case linear time? I understand that there is some sort of substitution that needs to take place, but I am shaky on how to come to the conclusion.

EDIT

I think I may have found what I was looking for, but I'm not entirely sure.

If you define worst case time complexity as W(s), the maximum number of steps done by an algorithm for an input size of s, then by definition of input size, s = lg n, where n is the input. Then, n = 2^s, leading to the conclusion that the time complexity is W(2^s), an exponential complexity. Therefore, the algorithm's performance with binary encoding is exponential, not linear as it is in terms of magnitude.

Answer 1

When talking about time complexity we usually use n as input, which is not a precise measure of the actual input size. I am having trouble showing that, when using specific size for input (s) an algorithm remains in the same complexity class.

For instance, take a simple Sequential Search algorithm. In its worst case it takes W(n) time. If we apply specific input size (in base 2), the order should be W(lg L), where L is the largest integer.

L is a variable that represents the largest integer. n is a variable that represents the size of the input. L is not a specific value anymore than n is.

When you apply a specific value, you aren't talking about a complexity class anymore, you are talking about an instance of that class.

Let's say you are searching a list of 500 integers. In other words, n = 500

The worst-case complexity class of Sequential Search is O(n)

The complexity is n

The specific instance of worst-case complexity is 500

---

Edit:

Your values will be uniform in the number of bits required to encode each value. If the input is a list of 32bit integers, then c = 32, the number of bits per integer. Complexity would be 32*n => O(n).

In terms of L, if L is the largest value, and lg L is the number of bits required to encode L, then lg L is the constant c. Your complexity in terms of bits is O(n) = c*n, where c = lg L is the constant specific input size.

Answer 2

As Lucia Moura states: "Except for the unary encoding, all the other encodings for natural numbers have lengths that are polynomially related"

Here is the source. Take a look at page 19.

Answer 3

What I know is that the maximum number of steps done by Sequential Search is, obviously, cn^2 + nlg L. cn^2 being the number of steps to increment loops and do branching.

That's not true at all. The maximum number of steps done by a sequential search is going to be c*n, where n is the number of items in the list and c is some constant. That's the worst case. There is no n^2 component or logarithmic component.

For example, a simple sequential search would be:

for (int i = 0; i < NumItems; ++i)
{
    if (Items[i] == query)
        return i;
}
return -1;

With that algorithm, if you search for each item, then half of the searches will require fewer than NumItems/2 iterations and half of the searches will require NumItems/2 or more iterations. If an item you search for isn't in the list, it will require NumItems iterations to determine that. The worst case running time is NumItems iterations. The average case is NumItems/2 iterations.

The actual number of operations performed is some constant, C, multiplied by the number of iterations. On average it's C*NumItems/2.