CODEWITHSUNDEEP
performancealgorithm
fibono
fibono

Reputation: 783

Time complexity of unknown element in n-element array

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!

Upvotes: 0

Views: 195

Answers (2)

amit
amit

Reputation: 178451

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.

Upvotes: 1

Scott Hunter
Scott Hunter

Reputation: 49803

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.

Upvotes: 0

Related Questions