"twoSum" solution and Big O Time Complexity explanation

CryroByte 0
Viewed 31

I was messing around with possible "twoSum" solutions because I'm pretty bored... Anyways I'm pretty new to "Big O Time Complexity", and I was trying to figure out the time complexity of my program.

Now I don't assume my solution is at all polished or better, I was just wanting some help finding out the time complexity of it. I am very new to BIG(O) so don't dog on my skills... you can roast my code if you wish.

    public static void main(String[] args) {
        int[] array = {5, 3, 4, 1, 5, 2, 1, 6, 3, 2};
        System.out.println(Arrays.toString(twoSum(array, 6)));
    }

    public static int[] twoSum(int[] nums, int target) {
        int oldValue = 0;
        int newValue;
        int currentValue;

        for (int i = 0; i < nums.length; i++) {
            currentValue = i;
            if (currentValue != 0) { // so oldValue never causes an exception
                oldValue = i - 1;
            }
            newValue = i + 1;

            if ((nums[currentValue] + nums[oldValue]) == target) {
                return new int[]{currentValue, oldValue};
            }

            if ((nums[currentValue] + nums[newValue]) == target) {
                return new int[]{currentValue, newValue};
            }

            if ((nums[newValue] + nums[oldValue]) == target) {
                return new int[]{newValue, oldValue};
            }
        }

        return new int[]{0, 0}; // we print out 0 0 if we can't find a solution
    }

This really won't have an ANSWER, as I don't know how time complexity works fully (as of right now) all I am asking for is someone to help me with an explanation

big-o java
1 Answers

From what I understand, you are trying to find 2 consecutive numbers in an array whose sum is equal to the target

Firstly, you don't need to use oldValue and newValue, since when currentValue = 2, oldValue will be equal to 1, which is basically checking the same pair of numbers as when currentValue = 1 and newValue = 2. The better version of your code should be:

    public static void main(String[] args) {
        int[] array = {5, 3, 4, 1, 5, 2, 1, 6, 3, 2};
        System.out.println(Arrays.toString(twoSum(array, 6)));
    }

    public static int[] twoSum(int[] nums, int target) {
        int oldValue = 0;
        int newValue;
        int currentValue;

        for (int i = 0; i < nums.length - 1; i++) {
            currentValue = i;
            newValue = i + 1;

            if ((nums[currentValue] + nums[newValue]) == target) {
                return new int[]{currentValue, newValue};
            }
        }

        return new int[]{0, 0}; // we print out 0 0 if we can't find a solution
    }

Secondly, for time complexity, one trick I usually use is to look for loops in the code.

For my suggested code, in the worst case, it has to go through N - 1 = O(N) iterations and takes O(1) operation to execute each iteration. Therefore the time complexity is O(N) * O(1) = O(N).

For your original code, it has to go through N iterations in the worst case, and takes approximately double the number of operations to execute each iteration compared to my code. However, the number of iterations is still O(N) and the number of operations per iteration is still O(1), thus the time complexity of your code is also O(N) * O(1) = O(N)

Note

Having a loop doesn't always mean the number of iterations for that loop is O(N). For example:

for (int i = 1; i < 100; i++) {
   // do something
}

The time complexity for this loop is O(1), since the number of iterations is always 100 and is independent of any input value

for (int i = 1; i < n; i = i * 2) {
  // do something
}

The time complexity for this loop is O(log2(n)) = O(log(N) / log(2)) = O(log(N)) (since log(2)) is a constant)

Huỳnh Thái Dương0
Related