Big O for my binary search algorithm with for loop?

Question

I am trying to get my algorithm down to the lowest possible running time.

What is the running time of this algorithm; is it O(log n) or O(n log n) because of the for loop?

import java.util.Arrays;

public class countDifferenceBetweenTwoArrays {
  private static int countDifference(int[] arrayA, int[] arrayB) {
    int differenceCount = 0;
    for (Integer i : arrayA) {
      if (Arrays.binarySearch(arrayB, i) < 0) {
        differenceCount++;
      }
    }
    for (Integer i : arrayA) {
      if (Arrays.binarySearch(arrayB, i) < 0) {
        differenceCount++;
      }
    }
    return differenceCount;
  }

You shouldn't mix int and Integer if you don't need to. Use for (int i : arrayA) instead, otherwise java needs to autobox the int for each iteration of the loop. — bcorso
– bcorso, Commented Feb 17, 2016 at 4:47

c_dubs · Accepted Answer · 2016-02-17 03:19:07Z

2

Your implementation is O(nlog(n)). You iterate over each array, an operation that is O(n). In each iteration, you perform an O(log(n)) binary search operation. This gives you an O(nlog(n)) running time for processing each array. You do this twice, but we ignore the constant factor of 2, leaving us with O(nlog(n)) for the entire function.

answered Feb 17, 2016 at 3:19

c_dubs

3602 silver badges7 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

CarolineRudolph Over a year ago

Is it possible to get it down to O(n) time?

c_dubs Over a year ago

Yes, if you make creative use of a hash table.

CarolineRudolph Over a year ago

can you suggest any ideas?

c_dubs Over a year ago

Are you familiar with hashtables?

CarolineRudolph Over a year ago

I'm okay with them, any ideas? :D

|

OneCricketeer · Accepted Answer · 2016-02-17 05:04:41Z

1

You need to take the symmetric difference between the sets to get the unique elements in each. In Java, this is done with Set#removeAll.

private static int distinctNumberOfItems(int[] arrayA, int[] arrayB) {

    HashSet<Integer> setA = new HashSet<Integer>();
    HashSet<Integer> setB = new HashSet<Integer>();
    HashSet<Integer> setC = new HashSet<Integer>();

    for (int i : arrayA) {
        setA.add(i);
        setC.add(i);
    }
    for (int i : arrayB) {
        setB.add(i);
    }

    setA.removeAll(setB);
    setB.removeAll(setC);
    return setA.size() + setB.size();
}

edited Feb 17, 2016 at 5:04

answered Feb 17, 2016 at 4:50

OneCricketeer

193k20 gold badges146 silver badges276 bronze badges

14 Comments

CarolineRudolph Over a year ago

You still need a copy HashSet C to copy all the distinct values from HashSet A and B. Then you need to perform your removeAll method. But then, there's still no performance improvement? It's still going to be O(n).

CarolineRudolph Over a year ago

Is there a way to bring it down to O(log n) instead of O(n)?

bcorso Over a year ago

You can't get O(logn) given that you need to at least loop over every element to see if it's in the other. However, O(n) is an improvement over your original code, which is O(nlogn).

bcorso Over a year ago

btw, this won't work for arrays with duplicate elements. However, you could build up a histogram of counts (Map<Integer, Integer>) to still get O(n).

OneCricketeer Over a year ago

@CarolineRudolph Huh? You don't need a HashSet C... And O(n) is the lowest you can do to find all distinct elements because you have to iterate over the all the elements from at least one list.

|

CarolineRudolph · Accepted Answer · 2016-02-17 05:43:49Z

1

Hash table for checking collisions between integers.

returns the number of distinct integers in both arrays

  private static int distinctNumberOfItems(int[] arrayA, int[] arrayB) {

    HashSet<Integer> setA = new HashSet<Integer>();
    HashSet<Integer> setB = new HashSet<Integer>();

    for (int i : arrayA) {
      setA.add(i);
      setB.add(i);
    }

    for (int i : arrayB) {
      setB.add(i);
      if (setA.contains(i))
        setB.remove(i);
    }
    System.out.println(setB);
    return setB.size();
  }
}

edited Feb 17, 2016 at 5:43

answered Feb 17, 2016 at 4:19

CarolineRudolph

1011 silver badge12 bronze badges

16 Comments

OneCricketeer Over a year ago

You seem to have posted this is the answer section, but asked a question. If you are trying to ask another question, you may make a new post

CarolineRudolph Over a year ago

It's nearly an answer, just that there's no getInt for HashSets

OneCricketeer Over a year ago

Technically, there isn't a getInt on booleans because that what you are calling that method on

CarolineRudolph Over a year ago

@cricket_007 How may I implement similar logic?

OneCricketeer Over a year ago

I don't know what logic that is. Why do you need getInt? The j variable is the only int that you have access to in that loop. I think you mean setA.contains(j)

|

Collectives™ on Stack Overflow

Big O for my binary search algorithm with for loop?

3 Answers 3

7 Comments

14 Comments

16 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

7 Comments

14 Comments

16 Comments

Your Answer

Sign up or log in

Post as a guest

Related