CODEWITHSUNDEEP
algorithmbig-o
user1099123
user1099123

Reputation: 6683

What is the big O of this substring + concatenation algo?

I struggle with Big O complexity and this type of algo always confused me. We are looping through every number here in 2 loops so its O(n^2). But inside each iteration of the loops we have a substring + a concatenation. From what I understand the concatenation is optimized by the compiler to use essentially a string buffer. Does the substring just count as 4*n? So the total compute is nn(n+(4*n)) OR O(n^3). (n+(4*n)) comes from concatenation + the 4 substrings. Is my evaluation correct?

I am trying to solve this problem: https://leetcode.com/problems/maximum-swap

public int maximumSwap(int num) {
        int biggestNum = num;
        String sNum = String.valueOf(num);
        for(int i = 0; i < sNum.length()-1; i++) {
            for(int j = i+1; j < sNum.length(); j++) {
                // 27364
                String jSuffix = j == sNum.length()-1 ? "" : sNum.substring(j+1);
                int newNum = Integer.valueOf(sNum.substring(0, i) + sNum.charAt(j) + sNum.substring(i+1, j) + sNum.charAt(i) + jSuffix);
                if(newNum > biggestNum) biggestNum = newNum;
            }
        }
        return biggestNum;
    }

Upvotes: 0

Views: 117

Answers (2)

ZhaoGang
ZhaoGang

Reputation: 4915

What is the big O of this substring + concatenation algo?

---IMHO, the + opreation time complexity is O(n).

From what I understand the concatenation is optimized by the compiler to use essentially a string buffer.

--- We can not assume the compiler will do the optimization, see this link. Even if it does, it compile to a StringBuider, not StringBuffer. They are different. If the compiler does not do the optimization, the time should be O(n), it will copy the whole string for each + operation.see this link.

Does the substring just count as 4*n? So the total compute is nn(n+(4*n)) OR O(n^3). (n+(4*n)) comes from concatenation + the 4 substrings. Is my evaluation correct?

--- IMHO, Java String operations such as substring will cost O(n) time, see this link, and the + operation also cost O(n), the time complexity of int newNum = Integer.valueOf(sNum.substring(0, i) + sNum.charAt(j) + sNum.substring(i+1, j) + sNum.charAt(i) + jSuffix); should be O(6n)(4n for 4 +, 2n for 2 substring)

Upvotes: 0

Lorenz
Lorenz

Reputation: 1323

This is correct, even if the string concatenation were not optimized by the compiler.

But as kaya3 noted, every input you give to this algorithm can have at most 10 (decimal) digits, which means n can be at most 10 anyways. Taking this into account the run-time is actually in O(1), since you can determine a priori an upper bound on the number of elementary operations this algorithm will execute.

If the argument were a BigInteger, run-time analysis would become more meaningful. Then you would also have to think about how long comparisons or Integer.valueOf(string) (or rather, the BigInteger equivalent new BigInteger(string)) take. The latter is probably in O(n^2) if you give it an input with n digits, which means the whole algorithm would run in O(n^4).

Upvotes: 1

Related Questions