Array jumping question. Please see details

The answer is: yes, because the "naive method" will give your O(N) time complexity anyway. In fact, all non-nonsense algorithm will give you O(N). It's easy to understand why: 1) given known index in the array, the time complexity of taking the element is always O(1) (that is, a constant), due to the nature of arrays, 2) you have to visit each element exactly once; hence O(N). You simply have no essential choice.

However, I suspect your problem is not correctly formulated. It's hard to imagine that the problem formulated in such "sophisticated" way could be so trivial. This comes from this part of formulation "An array of size n is given. The array can be traversed by jumps of size <= k". It simply means that you can always choose the "jump size" of 1, which is less then k. (Of course, for k < 1 the solution does not exist, but for all other integer k the solution is achieved with "jump size" == 1, and you cannot improve this result.) You simply traverse all the array from first to last element. The solution cannot be improved.

At the same time, next part of the formulation is pure nonsense: "a jump can land you anywhere from i+1 to i+k index". For "jump size" other then 1, there would not be away to jump back. You did not include negative jumps. Your k should be understood as an absolute value. You certainly mean from i-k to i-1 and from i+1 to i+k. Only this way, the solution "1 + 2 + 7 + 1" you demonstrated could be considered valid: it is based on k = 2, and "jump size" = 2 and -2. Of course, for "jump size" = 1, this is not a problem.

Conclusions: 1) as formulated (excluding contradictory part I discussed in the paragraph above), the problem is way too trivial to be serious and is solved by using 1, traversing all elements from first to last, which gives O(N); 2) if you correct your formulation to something non-contradictory and not so trivial, but having a solution for all arrays and some valid k, any of such solutions will always give you O(N), by the reasons I explained in my first paragraph above.

I understand that the statement #2 requires stricter proof, because I touched such problem as some class of some hypothetical problems, so we can only discuss it seriously if you want to fix the formulation to something less trivial. So, consider this part as just an idea. I would assume less trivial problem which can appear if you replace "jumps of size <= k" with "-k < jump < k, where k > 1", and the lengths of arrays are limited accordingly, to make the problem solvable. Also, you have to formulate if the "jump size" can be modified jump to jump, or it should be the same for all jumps.

—SA