Why is this time complexity O(total*n)?

Question

Namely I’m having trouble understanding why at worst case running that blue part takes (total⋅n⋅2)+1 steps.

Here is the code of the function:

The video this screenshot is from can be found at https://www.youtube.com/watch?v=nqlNzOcnCfs.

Answer 1

I did not watch the video you linked. However, looking at the code, this looks like it's computing the number of distinct ways to making up the value total using coins in denominations given by the array arr.

The function dp essentially fills a dictionary mem with values. The dictionary mem is indexed by total and i. Over the recursive calls, total and i might (and will) become smaller. The new values taken by total will be in range [0; total]. The new values taken by i will be in range [0; arr.length - 1].

Hence the number of possible different keys for the dictionary is at most (total+1) * arr.length

Calls to dp with a pair of values for total and i which is already in the dictionary do not result in further recursive calls. Hence the number of calls to dp which result in further recursive calls is at most (total+1) * arr.length.

Since each call to dp results in at most 2 further recursive calls, the total number of calls to dp is at most 2 * (total+1) * arr.length. Which is O(total * arr.length). Which I assume is what you call O(total * n).