Complexity is typically expressed in big O or big omega notation

• Big O describes the maximum operations for the worst performance
  - O(n), O(n^2), etc.
• Big omega describes the minimum operations for the best performance

시간 복잡도 (Time complexity)

How long it takes to run an algorithm

• Every operation takes "1" time to perform
• A for function performs an operation N times, where N is the length of an array
  - If a for function is inside a for function, it would perform the operation N^2 (N * N) times
• An if function performs an operation 1 time
  - If an if function is inside a for function, it would take 1 * N times
  • For example, if there are two more operations to perform in the if function, it would take 3 * N times

Example

1. Finding the most used alphabet in a string:

for alphabet in alphabet_array:    # alphabet_array 의 길이(26)만큼 아래 연산이 실행
	occurrence = 0                  # 대입 연산 1번 실행
    for char in string:             # string 의 길이만큼 아래 연산이 실행
		if char == alphabet:        # 비교 연산 1번 실행
		occurrence += 1         	# 대입 연산 1번 실행 

    if occurrence > max_occurrence: # 비교 연산 1번 실행
		max_alphabet = alphabet     # 대입 연산 1번 실행
		max_occurrence = number     # 대입 연산 1번 실행

for alphabet = 26
One operation = 1
for char = O(N) where N is the string length
One if operation = 1
One operation = 1
One if operation = 1
Two operations = 2
26 (1 + 2 N + 3) = 52N + 104

2. Gives same result as 1, written differently

for char in string:        # string 의 길이만큼 아래 연산이 실행
    if not char.isalpha(): # 비교 연산 1번 실행
        continue
    arr_index = ord(char) - ord('a')         # 대입 연산 1번 실행 
    alphabet_occurrence_list[arr_index] += 1 # 대입 연산 1번 실행 

max_occurrence = 0        # 대입 연산 1번 실행 
max_alphabet_index = 0    # 대입 연산 1번 실행 
for index in range(len(alphabet_occurrence_list)):    # alphabet_array 의 길이(26)만큼 아래 연산이 실행
    alphabet_occurrence = alphabet_occurrence_list[index] # 대입 연산 1번 실행 
    if alphabet_occurrence > max_occurrence: # 비교 연산 1번 실행 
        max_occurrence = alphabet_occurrence # 대입 연산 1번 실행 
        max_alphabet_index = index           # 대입 연산 1번 실행 

for char = O(N)
3 operations = 3
2 operations = 2
for index = 26
4 operations = 4

3 N + 2 + 26 4 = 3N + 106

Polynomial operations (N^2) are much longer than linear operations (N).

Time complexity is more important than space complexity.

공간 복잡도 (Space complexity)

The memory space required to solve an instance.
One data takes "1" space.

Example

alphabet_array = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "x", "y", "z"]
# -> 26 개의 공간을 사용합니다
max_occurrence = 0 # 1개의 공간을 사용합니다
max_alphabet = alphabet_array[0]   # 1개의 공간을 사용합니다.

for alphabet in alphabet_array:
    occurrence = 0  # 1개의 공간을 사용합니다

Takes a total of 26 spaces.

alphabet_occurrence_list = [0] * 26 # -> 26 개의 공간을 사용합니다

for char in string:
    if not char.isalpha():
        continue
    arr_index = ord(char) - ord('a')  # 1개의 공간을 사용합니다
    alphabet_occurrence_list[arr_index] += 1

max_occurrence = 0                   # 1개의 공간을 사용합니다
max_alphabet_index = 0               # 1개의 공간을 사용합니다
for index in range(26):
    alphabet_occurrence = alphabet_occurrence_list[index] # 1개의 공간을 사용합니다
    if alphabet_occurrence > max_occurrence:
        max_occurrence = alphabet_occurrence
        max_alphabet_index = index

Takes a total of 30 spaces.

However, both examples take a constant number of space, so time complexity should be compared between the two codes instead of space complexity.