CODEWITHSUNDEEP
algorithmiterationtime-complexity
Vishal Singh
Vishal Singh

Reputation: 45

Is it linear Time Complexity of Bigger?

Can any one tell me what is the worst time complexity of below code? Is it linear or bigger?

void fun(int[] nums){
{
  int min = min(nums);
  int max = max(nums);
  for(int i= min; i<=max;i++){
    print(i); //constant complexity for print
  }
}
int min(int[] nums);//return min in nums in linear time
int max(int[] nums);//return max in nums in linear time

where 0 <= nums.length <= 10^4 and -10^9 <= nums[i] <= 10^9

Can I say that time complexity of this code is O(Max(nums[i]) - Min(nums[i])) and can I say, this is linear time complexity?

Upvotes: 1

Views: 172

Answers (2)

Damien
Damien

Reputation: 4864

As the complexity is linear with respect to the range R = max - min of the data, I would call it a pseudo-linear complexity. O(N + R).

This is detailed in this Wikipedia entry: Pseudo-polynomial time

As mentioned in the introduction of this article:

In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is a polynomial in the numeric value of the input (the largest integer present in the input)—but not necessarily in the length of the input (the number of bits required to represent it), which is the case for polynomial time algorithms.

Generally, when analysing the complexity of a given algorithm, we don't make any specific assumption about the inherent range limitation of a particular targeted language, except of course if this is especially mentionned in the problem.

Upvotes: 3

derpirscher
derpirscher

Reputation: 17407

If the range of numbers is constant (ie -10^9 <= nums[i] <= 10^9) then

for(int i= min; i<=max;i++){
  print(i); //constant complexity for print
}

is in O(1), ie constant because you know, it iterates at most 2 * 10^9 numbers, regardless of how many numbers there are in the nums[] array. Thus it does not depend on the size of the input array.

Consider the following input arrays

nums = [-10^9, 10^9];  //size 2
nums = [-10^9, -10^9 + 1, -10^9 + 2, ..., 10^9 - 2, 10^9 - 1, 10^9]  //size 2 * 10^9 + 1

for both min and max will have the same values -10^9 and 10^9 respectively. Thus your loop will iterate all numbers from -10^9 to 10^9. And even if there were 10^100000 numbers in the orginal array, the for loop will at most iterate from -10^9 to 10^9.

And you say min() and max() are in O(n), thus your overall algorithm would also be in O(n). But if you then take into account that the given maximum length (10^4) of the array is by magnitudes smaller then the limit of your numbers, you can even neglect calling min and max

And as for your comment

For ex. array =[1,200,2,6,4,100]. In this case we can find min and max in linear time(O(n) where n is length of array). Now, my for loop complexity is O(200) or O(n^3) which is much more than length of array. Can I still say its linear complexity

The size of the array and the values in the array are completely independent of each other. Thus you cannot express the complexity of the for loop in terms of n (as explained above). If you really want to take into account also the range of the numbers, you have to express it somehow like this O(n + r) where n is the size of the array, and r is the range of the numbers.

Upvotes: 2

Related Questions