What is the Time and space Complexity of maxOccuringDigit() function?

user_8327440 0
Viewed 60
static int maxOccuringDigit(int n) {
    int tempNum = n;
    if (tempNum < 0)
        tempNum = -tempNum;

    int[] count = new int[10];

    while (tempNum != 0) {
        int rem = tempNum % 10;
        count[rem] = count[rem] + 1;
        tempNum = tempNum / 10;
    }

    int maxCount = count[0];
    int digit = 0;
    for (int i = 1; i < count.length; i++) {
        if (count[i] > maxCount) {
            maxCount = count[i];
            digit = i;
        } else if (count[i] == maxCount)
            digit = -1;
    }
    return digit;
}

The task is to find which digit occurs maximum times. I need help in analyzing the time complexity of this function. I think it should be O(k) where k is the total digits in given number n. Mainly I am curious about the time complexity of for loop used here. As it will always loop for 10 times, can we consider it as constant time operation?

So total O(k + 10) ~ O(k) time. Is that correct?

Also for space complexity it is using 10 extra spaces of array only, so what will be its space complexity too?

big-o time-complexity function arrays java
2 Answers

The while loop will run log10(N) times. Yes, the for loop is run once for N and the fact that it runs 10 times is negligible, i.e. C = 10.

So the runtime complexity of your method is log10(N) + C and as C is negligible, log10(N) is its runtime complexity.

Space complexity is O(1).

user_5449830

The first loop depends on the number of digits, k, and is O(k). The second loop depends on the number of elements in the count array, which is 10. Since that's a constant, it runs in O(1). The overall time complexity is therefore O(k).

Space complexity is O(1) for the same reason as why the time complexity for the second loop is O(1).

user_150102150
Related