Time and complexity of an integer array

Question

I am working on an assignment and don't get answer for some of questions.

I Have been asked :

Input: an array A of length N that can only contain integers from 1 to N

Output: TRUE - A contains duplicate, FALSE - otherwise.

I have created a class which is passing my test cases.

public class ArrayOfIntegers {


public boolean isArrayContainsDuplicates(int [] intArray){
    
    int arraySize = intArray.length;
    
    long expectedOutPut = arraySize*(arraySize+1)/2;
            
    long actualOutput = 0;
    
    for(int i =0 ; i< arraySize; i++){
        
        actualOutput =  actualOutput + intArray[i];
        
    }
            
    if(expectedOutPut == actualOutput)
        return false;
    
    return true;
}   

}

Now further questions on this

1. Is it possible to provide the answer and NOT to destroy the input array A?

   I have not destroy an array. So what I have done is correct?

2. Analyze time and space complexity of your algorithm?

   So do I need to write something about the for loop that as soon as I find the duplicate elements I should break the loop. Frankly speaking I am not very clear about the concept of time and space complexity.

3. Is O(n) for both time and space possible?

   is this should be No as n could be any number. Again , I am not very clear about O(n).

Thanks

Answer 1

Is it possible to provide the answer and NOT to destroy the input array A?

Yes. For example, if you don't care about the time it takes, you can loop over the array once for every possible number and check if you see it exactly once (if not, there must be a duplicate). That would be O(N^2).

Usually, you would use an additional array (or other data structure) as a scratch-list, though (which also does not destroy the input array, see the third question below).

Analyze time and space complexity of your algorithm?

Your algorithm runs in O(n), doing just a single pass over the input array, and requires no additional space. However, it does not work.

Is O(n) for both time and space possible?

Yes.

Have another array of the same size (size = N), count in there how often you see every number (single pass over input), then check the counts (single pass over output, or short-circuit when you have an error).

So do I need to write something about the for loop that as soon as I find the duplicate elements I should break the loop.

No. Complexity considerations are always about the worst case (or sometimes the average case). In the worst case, you cannot break out of the loop. In the average case, you can break out after half the loop. Either way, while being important for someone waiting on a real-life implementation to finish the calculation, this does not make a difference for scalability (complexity as N grows infinite). Constant offsets and multipliers (such as 50% for breaking out early) are not considered.

Answer 2

As hints:

1. Yes, it is possible to provide an answer and not destroy the array. Your code^* provides an example.

2. Time complexity can be viewed as, "how many meaningful operations does this algorithm do?" Since your loop goes from 0 to N, at minimum, you are doing O(N) work.

   Space complexity can be viewed as, "how much space am I using during this algorithm?" You don't make any extra arrays, so your space complexity is on the order of O(N).

3. You should really revisit how your algorithm is comparing the numbers for duplicates. But I leave that as an exercise to you.

^{*: Your code also does not find all of the duplicates in an array. You may want to revisit that.}

Answer 3

public boolean hasDuplicates(int[] arr) {
    boolean found = false;
    for (int i = 1 ; i <= arr.length ; i++) {
        for (int a : arr) 
            if (a == i) found = true;
        if (! found) return true;
    }
    return false;
}

I believe this method would work (as yours currently doesn't). It's O(n^2).

I'm quite sure that it is impossible to attain O(n) for both time and space since two nested for-loops would be required, thereby increasing the method's complexity.

Edit

I was wrong (sometimes it's good to admit it), this is O(n):

public boolean hasDuplicates(int[] arr) {
    int[] newarr = new int[arr.length];
    for (int a : arr) newarr[a - 1]++;
    for (int a : newarr) if (a != 1) return true;
    return false;
}

1. Yes, the input array is not destroyed.
2. The method directly above is O(n) (by that I mean its runtime and space requirements would grow linearly with the argument array length).
3. Yes, see above.

Answer 4

It's possible by adding all of the elements to a hashset = O(n), then comparing the number of values in the hashset to the size of the array = O(1). If they aren't equal, then there are duplicates.

Creating the hashset will also take up less space on average than creating an integer array to count each element. It's also an improvement from 2n to n, although that has no effect on big-O.

Answer 5

1) This will not require much effort, and leaves the array intact:

 public boolean isArrayContainsDuplicates(int [] intArray){
  int expectedOutPut = (intArray.length*(intArray.length+1))/2;
  int actualOutput = 0;
  for(int i =0 ; i < intArray.length; i++){
   if(intArray[i]>intArray.length)return true;
   actualOutput += intArray[i];
  }
  return expectedOutPut == actualOutput ? false: true;
 }

2) This will require touching a varying amount of elements in the Array. Best case, it hits the first element which would be O(1), average case is it hits in the middle O(log n), and worse case is it goes all the way through and returns false O(n).

O(1) refers to a number of operations which are not related to the total number of items. In this case, the first element would be the only one which has this case.

O(log n) - log is a limiting factor which can be a real number from 0 to 1. Thus, multiplying by log will result in a smaller number. Hence, O(log n) refers to a required amount of operations which are less than the number of items.

O(n) - This is when it required a number of operations equal to the number of items.

These are all big-o notation for the required time.

This algorithm uses memory which will increase as n increases. However, it will not grow linearly but instead be a fraction of the size n is and therefore its spacial Big-O is O(log n).

3) Yes, this is possible - however, it is only possible in best-case scenarios.