This is part of my code, I was thinking about the time complexity of this block of code, could it be n^2? Although the inner for loop is conditioned, but the inner loop with if statement together will still be n, right? So the total Big-O will be n^2?

PIC

Code:

    for (int i = 0; i < s.length(); i  ) {
        if(Character.isDigit(s.charAt(i))) {
            count  = s.charAt(i);
        }else {
            for (int j = 1; j <= Integer.parseInt(count); j  ) {
                value = s.charAt(i);
                decodedStr.append(value);
            }
            count = "";
        }
    }

CodePudding user response：

The running time does not depend on the length of the string. More than that, it depends on the length of the string and on its content. Nevertheless we can try to analyze it.

The content seems to contain digits and non-digits. Each time a digit is encountered the count is appended that digit. If a non-digit is encountered then it executes an inner loop that goes from 1 till count.

One can try to think about what the worst input string could be. Assume the length of the string is n 1, and all digits are the maximum possible: 9.

If you have a string with all such digits except the last character, then you would count n digits, and count contains n of 9s. This is considerable larger than n.

Example:
n is 5 (e.g. input string is 99999x). Then count would be 99999. For the running time this would mean: the outer loop executes 6 times; its last execution contains the inner loop, which executes 99999 times. That is way more than n^2. That would make O(n count) where count can be calculated as 10^n - 1. So in the end the running time can be O(10^n).

Maybe it helps to try to see the following:

n=5 and count=99.999 => count = 10^5 - 1
n=10 and count=9.999.999.999 => count = 10^10 - 1

CodePudding user response：

Let's n be the length of the string and m the sum of all numbers in the string. For the string "foo10bar2" m is 12.

The complexity is simply O(n,m) = n m