title: Proving a Turing Machine counts in O(n)?
body: <p>So for the past few days I've been designing a Turing Machine and found out that with my implementation my counting in binary runs at about 4n, where n is the number I count up to. So O(4n) -> O(n). I am not very good at proving complexity, but from what I understand from research is that, if you have a Turing Machine, M, for each n in {0,1}*, t_{M}(n) will be how long it will take to count to n, correct? Then if it doesn't halt, then it's highest bound is infinity. Is there a way to make a bridge between these two to conclude that it is indeed worst case to have n steps? I am never sure where to start proofs, any ideas?</p>
  
  <p><strong>Update:</strong> </p>
  
  <p>Below is my Turing Machine representation for counting in binary:</p>
  
  <pre><code>import java.util.Scanner;
  public class TuringMachine {
  
  /**
   * Divide a number n by 2 shifting right (shift-right-logical) 
   * to figure out the minimum number of bits needed to represent
   * the number in binary.
   */
  private static int getNumBits(int n) {
      int c = 0;
      while (n &gt; 0) {
          c++;
          n = n &gt;&gt; 1;
      }
      return c;
  }
  
  private static void computeBinaryValues(int n) {
      System.out.println();
  
      int i, c, state;
      char symbol;
      String t;
  
      System.out.println("Computed binary values for:"); 
  
      // Compute values of n = 1 to n  
      for (int j = 1; j &lt;= n; j++) {
          t = ""; // temp string
          state = 0; // current state
          symbol = ' '; // current symbol being read
          c = getNumBits(j) + 1; // minimum number of bits needed + 1 for a buffer
          i = c - 1; // indexing starting from end of the string 
  
          // initialize temp string to contain all ' ' characters
          for (int k = 0; k &lt; c; k++) {
              t += " ";
          }
  
          // String builder off "empty" t string 
          StringBuilder s = new StringBuilder(t);
          // The actual binary representation of n + end space buffer
          String a = Integer.toBinaryString(j) + " ";
  
          // Turing Cycle  
          while (!(s.toString()).equals(a)) { // if the binary build is successful, these match.
              if (state == 0) {
                  if (symbol == ' ') {
                      state = 1;
                      i--; // left
                  } else { // symbols 0 and 1 rewrite themselves &amp;&amp; move right 1
                      i++; // right
                  } 
              } else if (state == 1) {
                  if (symbol == ' ') {
                      s.setCharAt(i, '1');
                      state = 0;
                      i++; // right
                  } else if (symbol == '0') {
                      s.setCharAt(i, '1');
                      state = 0;
                      i++; // right
                  } else {
                      s.setCharAt(i, '0');
                      i--; // left
                  }
              }
              symbol = s.charAt(i); // get symbol to read from
          }
          System.out.println(j + " -&gt; " + s); // print binary string created from machine
      }
  }
  
  public static void main(String[] args) {
      Scanner in = new Scanner(System.in);
      System.out.println("Enter value for n &gt;= 1: ");;
      computeBinaryValues(in.nextInt());
  }
  }
  </code></pre>
  
  <p>So, using Ishtar's suggestion for induction:</p>
  
  <p><code>C(0) = a</code>
  <code>C(1) = b</code>
  <code>C(2) = c</code></p>
  
  <p>Let k be a constant - assumed 4 from my experiments with my code.</p>
  
  <p><code>c = k + b</code>
  <code>b = k + a</code></p>
  
  <p>And he says we have to prove <code>c(i+1) = c(i) + k</code>then I gave my interpretation of what it meant? (I do not understand his case for induction)</p>