Direct Recursion vs While Loop for time complexity performance

Question

I was wondering how time complexity compares between these two methods. I have written the first findEmpty function and a friend wrote the 2nd. Both more or less achieve the same thing, however, I'm unsure which exactly computes faster (if at all) and why?

these examples come from an implementation of a hashtable class we've been working on. This function finds the next empty location in the array after the given parameters and returns it. Data is stored in the array "arr" as a Pair object containing a key and a value.

I believe this would run at O(1):

private int findEmpty(int startPos, int stepNum, String key) {
        if (arr[startPos] == null || ((Pair) arr[startPos]).key.equals(key)) {
            return startPos;
        } else {
            return findEmpty(getNextLocation(startPos), stepNum++, key);
        }
    }

I believe this would run at O(n):

private int findEmpty(int startPos, int stepNum, String key) {  
        while (arr[startPos] != null) {
            if (((Pair) arr[startPos]).key.equals(key)) {
                return startPos;
            }
            startPos = getNextLocation(startPos);
        }
        return startPos;
    }

here is the code for the Pair object and getNextLocation:

private class Pair {
        private String key;
        private V value;
        public Pair(String key, V value) {
            this.key = key;
            this.value = value;
        }
    }

private int getNextLocation(int startPos) {
        int step = startPos;
        step++;
        return step % arr.length;
    }

I expect my understanding is off and probably haven't approached this question as concisely as possible, but I appreciate and welcome any corrections.

bob tang · Accepted Answer · 2021-01-14 04:47:43Z

1

Your solution has the same time complexity as your friend's. Both are linear to the length of your array. recursion did not reduce your time complexity to O(1), as it keeps calling getNextLocation until it finds the key.

And also in your function, getNextLocation

private int getNextLocation(int startPos, int stepNum) {
    int step = startPos;
    step++;
    return step % arr.length;
}

the second parameter stepNum is never used in this function, and it should be cleared from all your functions to make it easier to read and understand. please write concise and clean code from the beginning.

answered Jan 14, 2021 at 4:47

bob tang

5933 silver badges12 bronze badges

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

1 Comment

Timbo Over a year ago

Thanks Bob, yeah sorry that was an oversight, it is actually used in reality but I cut things down a bit here to be more self contained and forgot that part!

Collectives™ on Stack Overflow

Direct Recursion vs While Loop for time complexity performance

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related