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

Question

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;
    }

There are some problems with your implementation details. `int` and `Integer.valueOf` are limited to `Integer.MAX_VALUE` which is a 10-digit number, so your code can't work for strings longer than that. That's OK since LeetCode won't give you such long strings, but it only makes sense to talk about big O notation when your input size is unbounded. — kaya3, Mar 02 '20 at 13:39

score 1 · Accepted Answer · answered Mar 02 '20 at 14:01

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

This is right - [here's a reference](https://stackoverflow.com/q/14757086/12299000) for `new BigInteger(String)`'s time complexity. — kaya3, Mar 02 '20 at 14:08

ZhaoGang · Answer 2 · 2020-03-02T14:45:38.330

0

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)

edited Mar 02 '20 at 14:45

answered Mar 02 '20 at 14:03

ZhaoGang

4,491
1
27
39

The details of how string concatenation is actually implemented are no longer specified as of Java 9+, but you can be sure that the time complexity to build a string of length n, using a constant number of concatenations, is O(n), for any sensible implementation of string concatenation. – kaya3 Mar 02 '20 at 14:04
`charAt` is definitely not O(n) time. – kaya3 Mar 02 '20 at 14:08
@kaya3 But `substring` should be a O(n) , not O(1) – ZhaoGang Mar 02 '20 at 14:13
Yes, but still not O(n^2) as you say the OP's loop body is. The OP's code does not do any quadratic-time operations inside the loop, but if it is adapted to use BigInteger then parsing the string would take quadratic time, as discussed in the other answer. – kaya3 Mar 02 '20 at 14:13
1

@kaya3 Yes, I think you are right. Consider `sNum.substring(0, i)+sNum.substring(i+1, j)`, it should be O(n+n+n), so should be still linear time. Thanks for pointing it out. – ZhaoGang Mar 02 '20 at 14:23

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

2 Answers2