[Python] Time Complexity: No String Concatenation!

Time Complexity

 In programming languages, time complexity is a measure of how much 'time' an algorithm consumes based on the size of the input (N). There are various notations, but commonly used ones include O(1), O(n), O(log n), and O(n^2).

---

Time Complexity Analysis through Examples

import sys

N = int(sys.stdin.readline())
result = ""

for i in range(N // 4):
    result += "long "

result += "int"

print(result)

 I will analyze the time complexity of my submitted code for BOJ problem 25314. The program appends the str 'long ' to the result N // 4 times based on the input value N, and finally adds "int" at the end before printing the result. Next, I will break down the code and examine the time complexity of each part.

N = int(sys.stdin.readline())

 The part that reads user input and converts it to an int has a time complexity of O(1).

result = ""

 The part that initializes the str of the result variable has a time complexity of O(1)."

for i in range(N // 4):
    result += "long "

 The part where the for loop runs N // 4 times involves adding the str 'long ' to the result variable. The key point here is that in Python, strings are immutable objects, which means a new str is created each time. For reference, the time complexity of str concatenation is O(m), where m is the length of the resulting concatenated str.

 

 In the for loop presented, str concatenation is repeated. Specifically, the time for the first concatenation is O(5), the second is O(10), the third is O(15), and so on. For the k-th concatenation, the time required is O(5k).

 

 Therefore, the total time complexity is T = O(5) + O(10) + O(15) + ... + O(5k). Simplifying this expression gives us T = O(5) * (1 + 2 + 3 + ... + k), which ultimately leads to T = O(5) * k(k + 1) / 2. Substituting k = N // 4 yields a final time complexity of O(n^2).

---

Using Lists to Improve Time Complexity

import sys

N = int(sys.stdin.readline())
result = []

for i in range(N // 4):
    result.append("long ")

result.append("int")

print("".join(result))

 The part involving repeated str concatenation is inefficient, so I modified the code to add elements to a list instead and then use the join() method to create the final str.

 

 However, even with this improvement, I still wonder if it’s necessary to use a loop at all. Using a list instead of a str may also lead to unnecessary memory usage.

---

What if we eliminate the loop entirely and don't use lists?

import sys

N = int(sys.stdin.readline())
count = N // 4
result = "long " * count + "int"

print(result)

 I removed the list and loop to reduce execution time. While theoretically the time complexity may not change, I believe it will be slightly better in practical use. Now, all that’s left is to test the actual execution time.

---

Average Execution Time Experiment

Test Case 1

Test Case 2

Test Case 3

---

Conclusion

 In the case of the third experiment, where I speculated that removing the list and loop would lead to improvements, the execution time showed only a very slight enhancement compared to the first experiment. It can be considered almost insignificant.

 

 The key takeaway from this experiment is that when concatenating strings, it is much more efficient to create a list, add elements to it, and then use the join() method to form a single str, rather than using string concatenation operations. (String concatenation exists for convenience, but it is not the optimal method.)

 

 It’s somewhat ironic that using string concatenation can be inefficient for combining strings. However, it’s important to recognize that the main reason for this result is that strings are immutable objects.