java - 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.

question from:https://stackoverflow.com/questions/65713134/direct-recursion-vs-while-loop-for-time-complexity-performance

Answer 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.