[CS] Complexity of Algorithms

1. What is an Algorithms?

An algorithm is a set of procedures of methods for solving any problems in mathematics, computer science, lingustics, or related fields. It refers to a step-by-step procedure for executing a calculation and also refers to a set of program instructions.

 

2. Time Compleixty of Algorithms

Time comlexity refers to a functional relationship between the time it takes to solve a problem and the input. In other words, when an algorithm is configured to solve a problem, it means how long it will take to perform an operation according to a change in an input value.

 

The time compleixty is basically calculated based on the Worst-case complexity. In other words, even for the if statement, the time complexity is calculated under the assumption that all values pass through the if statement.

 

def maximum(values):
    answer = None                            # c1, 1 time,  c1
    for value in values:                     # c2, N times, c2*N
        if answer == None or answer < value: # c3, N times, c3*N
            answer = value                   # c4, N times, c4*N
    return answer                            # c5, 1 time,  c5

 

The time complexity varies depending on the type of operation and the presence or absence of an input value. While accurate time complexity can be considered when calculating the time complexity in a single line of code, it is difficult to calculate the exact time complexity as the code inside the algorithm becomes longer and more complexity.

 

At this time, a method for approximately expressing time complexity is Big-O notation.

 

Kinds of the time complexity	Notation
Constant Time Complexity	\(O(1)\)
Linear Time Complexity	\(O(N)\)
Polynomial Time Complexity	\(O(N^c)\)
Logarithmic Time Complexity	\(O(log(N))\)

 

Constant Time Complexity refers to the basic operations of a computer, storing values in storage locations, and operating rules. There is an amortized analysis, a complexity that is considered similar to the constant time complexity. In the case of amortization analysis, the calculating with the worst selection complexity has the time complexity of O(N), but if only a smaller portion of the operation has the execution unit of N, the time complexity is considered as average.

 

A representative algorithm of Logarithmic Time Complexity is the binary search algorithm. Binary search algorithm is an algorithm that find values efficiently by considering only half the index by using the advantages of an ordered list as an algorithm to locate specific values in an ascending order.

 

3. Space Complexity of Algorithms

Space complexity is the amount of resource space required to execute and complete a program, and refers to the size (variable, list) of memory corresponding to an algorithm. Space complexity and time complexity are inversly proportional to each other, and increasing time complexity reduces the size of space complexity, and increasing space complexity decrease the size of time complexity. By appropriately balancing this, an algorithm having efficient memory and fast execution time ccan be established.

 

Examples of understanding trade-off between time complexity and space complexity

# No preprocessing algorithm for the sums of pairs problem:
def find_sums(values, target_sums):
    sums = {}
    for target in target_sums:
        sums[target] = False
        for i in range(len(values)):
            for j in range(i, len(values)):
                if values[i] + values[j] == target:
                    sums[target] = True
    return sums

# Full preprocessing algorithm:
def find_sums_precompute(values, target_sums):
    possible_sums = set()
    for i in range(len(values)):
        for j in range(i, len(values)):
            possible_sums.add(values[i] + values[j])
    sums = {}
    for target in target_sums:
        sums[target] = target in possible_sums
    return sums

# Balanced algorithm:
def find_sums_balanced(values, target_sums):
    value_set = set(values)
    sums = {}
    for target in target_sums:
        for value1 in values:
            value2 = target - value1
            sums[target] = value2 in value_set
    return sums