title: Problem size and input pre-process costs in finding time complexity of an algorithm
body: <p>I read different topics about time complexity on algorithms. I try to understand and learn how to analyze algorithms, but I still have some concerns. Therefore, I hope that this topic will help to make them clear.</p>
  <p>Here is a problem:</p>
  <blockquote>
  <p>Give an integer <strong>n</strong> (1 ≤ n ≤ 10^18). Removing digits at any positions from <strong>n</strong> to create new numbers. Find the largest cube number from those numbers including <strong>n</strong>. If there is no any cube number, return <strong>-1</strong>.</p>
  </blockquote>
  <p>And below is a solution.</p>
  <p><div class="snippet" data-lang="js" data-hide="false" data-console="true" data-babel="false">
  <div class="snippet-code">
  <pre class="snippet-code-js lang-js prettyprint-override"><code>let maxCubeNum = -1;
  
  function isCubeNumber(num) {
    let x = Math.round(Math.pow(num, 1 / 3), 0);
    return x * x * x === num;
  }
  
  // generate the subset numbers from n's digits with recursion
  function findCubeNumber(digits) {
    if (digits.length == 0)
      return [0];
  
    // recursively find all subsets without the last digit
    let parts = findCubeNumber(digits.slice(0, -1));
  
    let nums = [];
    parts.forEach(part =&gt; {
      // case 1: with the last digit
      let num1 = part * 10 + digits.slice(-1)[0];
      // case 2: without the last digit
      let num2 = part;
  
      if (isCubeNumber(num1))
        if (num1 &gt; maxCubeNum)
          maxCubeNum = num1;
  
      if (num2 &gt; 0 &amp;&amp; isCubeNumber(num2))
        if (num2 &gt; maxCubeNum)
          maxCubeNum = num2;
  
      nums.push(num1);
      nums.push(num2);
    });
  
    return nums;
  }
  
  function findNumbers(n) {
    maxCubeNum = -1
    let digits = [];
  
    // split n to digits
    while (n &gt; 0) {
      digits.unshift(n % 10);  // insert to the first position of the list
      n = (n - n % 10) / 10;   // integer division by 10
    }
  
    // generate subset numbers and find the max cube number from those numbers
    findCubeNumber(digits);
  
    return maxCubeNum;
  }
  
  let ans = findNumbers(4125);
  document.write(ans);</code></pre>
  </div>
  </div>
  </p>
  <p>Note that, my point is analyzing the above algorithm to find its time complexity. I am not looking for a better algorithm.</p>
  <h1>My questions</h1>
  <h2>1. What is the problem size in the above algorithm?</h2>
  <p>It is <code>n</code> or <code>log10(n)</code> (<code>value</code> or <code>length of n</code>)?</p>
  <p>I'm quite confused since the problem can be resolved with a naive solution as following:</p>
  <pre><code>findCubeNumber(n) {
    for(i=n; i&gt;0; i--)
      if (i is_subset n and is_cube_num(i))
        return i;
  
    return -1;
  }
  </code></pre>
  <p>In this case, the problem size is apparently <code>n</code>. By this way, the above algorithm has size of <code>log10(n)</code> as it is based on the length of the number <code>n</code>.</p>
  <p>But if we consider the length of the input number as the problem size, the pseudo-code's size will be <code>10^n</code>.</p>
  <p>These will lead to different results of time complexity. Then, which of them is the problem size?</p>
  <h2>2. When we talk about the time complexity of an algorithm, we would include costs of pre-processing input data or not?</h2>
  <p>For example, in the above algorithm, I use a while-loop to split number <code>n</code> into digits. would I count it as a part of calculating time complexity?</p>
  <p>I have seen few topics around, one uses built-in function in a particular programming language to convert the number to string, considers it as a constant cost, and ignores it. Is that right?</p>
  <h2>3. What is the time complexity of the above algorithm?</h2>
  <h3>a. If the problem size is the length of number <code>n</code>, the costs are respectively:</h3>
  <p><code>2</code>   - the first two assignments in findNumbers()</p>
  <p><code>a*n</code> - a while-loop splitting number <code>n</code> into digits, a is a constant and represents to inner operators in while-loop of findNumbers().</p>
  <p>The time complexity of the recursive function would be:</p>
  <p><code>T(n) = 1 + T(n - 1) + 2^n</code></p>
  <p>Where,</p>
  <p><code>1</code> - The comparing operator to stop recursive function</p>
  <p><code>T(n - 1)</code> - call itself with the size reducing 1.</p>
  <p><code>2^n</code> - forEach loop steps which creating numbers by a combination of digits. Each digit will have two states: <code>present</code> (with the digit) and <code>absent</code> (without the digit).</p>
  <p>By induction: T(n) = 2^n * b + n + c (b, c are constants)</p>
  <p>Then the time complexity of the entire algorithm,</p>
  <p>T(n) = 2 + a*n + 2^n * b + n + c = T(2^n + n) = <strong>T(2^n)</strong></p>
  <h3>b. If the problem size is the value of number <code>n</code>, then</h3>
  <p>T(n) = 2 + a*log10(n) + 2^log10(n)*b + log10(n) + c = T(2^log10(n)) = T(2^log2(n)) = <strong>T(n)</strong></p>
  <p>Which is the right answer? or both of them wrong?</p>
  <p>Please help me to clarify it.</p>