title: Why does a more efficient algorithm run slower?
body: <p>I'm new here, and if my question is not relevant, please delete it. I had a doubt while solving the following problem on <a href="https://leetcode.com/" rel="nofollow noreferrer">LeetCode</a>:</p>
  
  <blockquote>
    <p>70 - Climbing Stairs:
    You are climbing a stair case. It takes N steps to reach to the top.
    Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?</p>
    
    <p><strong>Note:</strong> Given n will be a positive integer.</p>
  </blockquote>
  
  <p>Example 1:</p>
  
  <ul>
  <li>Input: 2</li>
  <li>Output: 2</li>
  </ul>
  
  <p>Explanation: There are two ways to climb to the top.</p>
  
  <ol>
  <li><p>One step <strong>then</strong> another step</p></li>
  <li><p>Two steps <strong>at a time</strong>.</p></li>
  </ol>
  
  <p>I know two solutions of this problem:</p>
  
  <ul>
  <li><p>One that calculates <strong>all possible step combinations</strong> at <strong>every step</strong>:</p>
  
  <pre><code>public class Solution {
      public int climbStairs(int n) {
          climb_Stairs(0, n);
      }
      public int climb_Stairs(int i, int n) {
          if (i &gt; n) {
              return 0;
          }
          if (i == n) {
              return 1;
          }
          return climb_Stairs(i + 1, n) + climb_Stairs(i + 2, n);
      }
  }
  </code></pre></li>
  <li><p>And another one that uses <strong>dynamic programming</strong>:</p>
  
  <pre><code>public class Solution {
      public int climbStairs(int n) {
          if (n == 1) {
              return 1;
          }
          int[] dp = new int[n + 1];
          dp[1] = 1;
          dp[2] = 2;
          for (int i = 3; i &lt;= n; i++) {
              dp[i] = dp[i - 1] + dp[i - 2];
          }
          return dp[n];
      }
  }
  </code></pre></li>
  </ul>
  
  <p>It is obvious that the second is much more efficient than the first. However, when I submit them, LeetCode shows nearly the same runtime, around 4ms. Shouldn't the second have a much shorter runtime than the first?</p>