title: Time Complexity Clarification on Algorithm
body: <p>Note: I've asked another question on this algorithm before, but this one is clarifying a time complexity question.</p>
  
  <p>Working on the following algorithm:</p>
  
  <blockquote>
    <p>Given an array of non-negative integers, you are initially positioned
    at the first index of the array.</p>
    
    <p>Each element in the array represents your maximum jump length at that
    position.</p>
    
    <p>Determine if you are able to reach the last index.</p>
    
    <p>For example:</p>
    
    <ul>
    <li><code>A = [2,3,1,1,4]</code>, return <code>true</code>.</li>
    <li><code>A = [3,2,1,0,4]</code>, return <code>false</code>.</li>
    </ul>
  </blockquote>
  
  <p>Below was my initial, brute force (with memoization) solution before I optimized according to my previous SO post <a href="https://stackoverflow.com/questions/42424607/speeding-up-solution-to-algorithm">Speeding up solution to algorithm</a> </p>
  
  <p>On that question, I had a discussion with a fellow user regarding the time complexity of my initial algorithm and I just wanted to make sure that I'm understanding correctly. The code below is an O(N) time algorithm correct? My code times out for big test inputs, so I'm assuming it's a really slow O(N)... but still  O(N) and not O(N^2) correct? Because the memoization saves away jumpable? for each index if I'm not mistaken..</p>
  
  <pre><code>@memo = {}
  def can_jump(nums)
      @memo = {}
      jumpable?(nums, 0) #new approach. launch a function for each index, memoize to get O(N) time. should be the same shit.
  end
  def jumpable?(nums, curr_idx)
      return true if curr_idx &gt;= nums.length - 1 || nums.length == 1
      i = curr_idx
      true_counter = 0
      curr_val = nums[i]
      curr_val.downto(1) do |num|
          @memo[curr_idx + num] ||= jumpable?(nums, curr_idx + num )
          true_counter +=1 if @memo[curr_idx + num]
      end 
      true_counter &gt; 0 
  end
  </code></pre>