title: Precise Input Size and Time Complexity
body: <p>When talking about time complexity we usually use <em>n</em> 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 (<em>s</em>) an algorithm remains in the same complexity class.</p>
  
  <p>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.</p>
  
  <p><strong>How do I show that Sequential Search, or any algorithm, remains the same complexity class, in this case linear time?</strong>  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.</p>
  
  <p><strong>EDIT</strong></p>
  
  <p>I think I may have found what I was looking for, but I'm not entirely sure.</p>
  
  <p>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 <em>size</em>, 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.</p>