I'm a newbie to time complexities and algorithms.
Say a method is passed an array, and we iterate through that array just once. I understand that the time depends on the size of the array--let's call that "n." But what if for each element "el" in that array, you do something "el" times? What would be the time complexity in this case, since you have another variable? Would it still be "n" since we only care about the variable in this case, which is the array size?
Thanks!
In this case, the time complexity is O(n*S), where S is the average value of the elements in the array.
You might want to ask:
Why the average and not max value?
Well, The time complexity is actually:
T = arr[1] + arr[2] + ... + arr[n] = (arr[1] + arr[2] + ... + arr[n])/n *n =
= S *n
The last equality is true since (arr[1] + arr[2] + ... + arr[n])/n=S by definition of average.
A common example of where something similar is seen is in the Dynamic Programming solution for Partition Problem, you create a 2-dimensional array of size SUM/2 * n (where SUM is the total sum of the array), and fill each entry in it incrementally, causing a O(n*SUM) solution.
Note that this is often regarded as a pseudo polynomial complexity, since it is not really polynomial in the size of the input.
O(n). But what if you cannot bound the size of the elements? In this case, complexity is dependent on the value, similar to the analysis of partition problem I linked to, which has runtime of (quote from wikipedia): This algorithm runs in time O(Nn), where n is the number of elements in the input set and N is the sum of elements in the input set.N is usually used to represent the size of the problem, and for problems like this, is often the size of the array. If we consider the contents of each element to be a number, there is a maximum to what that number can be, so we consider it a constant, and it does not play a role in the final complexity expression.
