# What is the algorithmic complexity of this?

I'm practicing leet code questions and want to understand more fully how to determine Big O notation. What is the algorithmic complexity of my solution to the following problem?

O(n^2) ? For every item in n I could loop an additional n[i] times. Or is it O(n) ?

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Input: [2,3,1,1,4]

Output: true

Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

var canJump = function(nums) {

let validIndices = {};
for(let i = nums.length - 1; i >= 0; i--) {
let currentNum = nums[i];
if(currentNum + i >= nums.length - 1) {
validIndices[i] = true;
} else {
while(currentNum > 0) {
if(validIndices[i + currentNum]) {
validIndices[i] = true;
}
currentNum--;
}
}
}

return !!validIndices[0];
};


Your algorithm has O(n^2) worst case complexity. You have a for loop of O(n). Inside your for loop you have a while loop which is O(currentNum). So if your currentNum is O(n) (ex nums[i] = length.nums for each i) then the complexity is O(n*n) = O(n^2).

Hint

Try not to recalculate things. You could use Dynamic programming technique. You need:

def canJump(i):
if valid[i] has been assigned a True or False value:
return valid[i]
#else calculate valid[i]
if i + nums[i] > len(nums):
valid[i] = True
return valid[i]
for jump in range(1, len(nums[i])):
valid[i] = any(False, canJump(i + jump))
return valid[i]

print(canJump(0))


This is just a pseudocode. I have not tried it. This way you only visit an element of nums once so it’s O(n).

[EDIT]
Actually I am wrong. My code is also O(n^2). Here is an O(n) solution.

at_least = n
for i from n-1 to 0:
if nums[i] + i >= at_least:
at_least = i
if at_least == 0: True else False


Now I think this is right. Sorry for the confusion. I got confused too.