Time complexity of a nested while loop-CodePudding

For the "longest common prefix" problem on Leetcode, Leetcode said that this solution is O(S) complexity where S is the sum of all characters. https://leetcode.com/problems/longest-common-prefix/solution/

Solution:

 public String longestCommonPrefix(String[] strs) {
    if (strs.length == 0) return "";
    String prefix = strs[0];
    for (int i = 1; i < strs.length; i  )
        while (strs[i].indexOf(prefix) != 0) {
            prefix = prefix.substring(0, prefix.length() - 1);
            if (prefix.isEmpty()) return "";
        }        
    return prefix;
}

Isn't a while loop inside of a for loop n^2 though? I thought all nested loops were n^2.

CodePudding user response：

For O(n) time complexity we must define n. It is typically the length of the input array. However in this case, we instead define S to be the sum of all characters as the length of the input array cannot accurately describe our time complexity.

The complexity of O(n^2) will be if we are iterating over the same array of length n with both the for loop and while loop.

CodePudding user response：

Isn't a while loop inside of a for loop n^2 though?

Not generally, but in this case you are right: the algorithm has a worst time complexity of O(