Analysis of Algorithms

Algorithm

An algorithm is a step-by-step procedure or set of rules for solving a problem or accomplishing a task. In computer science, algorithms are the fundamental building blocks for solving computational problems.

Algorithm should have the following five characteristic features:

1. Input:
   An algorithm takes zero or more inputs. These inputs are the initial data or parameters upon which the algorithm operates to produce the desired output.
2. Output:
   An algorithm produces at least one output, which is the result of processing the input according to the specified steps or rules.
3. Definiteness:
   Each step of the algorithm must be precisely and unambiguously defined. There should be no ambiguity or uncertainty about what actions to take at each stage of the algorithm.
4. Effectiveness:
   An algorithm should be effective, meaning it solves the problem it’s designed for using a finite amount of resources (such as time and memory). It should achieve its intended purpose efficiently.
5. Termination:
   An algorithm must terminate after a finite number of steps. It cannot run indefinitely. This ensures that the algorithm eventually produces the desired output and does not enter into an infinite loop or never-ending computation.

Complexity classes

Complexity classes are a way of categorizing computational problems based on their inherent difficulty and the resources required to solve them.

1. P: This class contains decision problems that can be solved by a deterministic Turing machine in polynomial time. Polynomial time means that the time required to solve the problem grows at most proportionally to some polynomial of the input size. These problems are considered efficiently solvable in practice.
2. NP: The class of problems for which a solution can be verified in polynomial time. In other words, even if we cannot efficiently find a solution to an NP problem, we can efficiently check if a proposed solution is correct. NP stands for “nondeterministic polynomial time,” indicating that solutions can be guessed and verified efficiently, although finding the solution itself may be hard. The class NP includes many important problems in various fields, such as the traveling salesman problem and the satisfiability problem.
3. NP-complete: This is a subset of NP problems that are considered among the hardest problems in NP. An NP-complete problem is one to which any other problem in NP can be reduced in polynomial time. If any NP-complete problem can be solved in polynomial time, then all problems in NP can be solved in polynomial time, implying P = NP.
4. NP-hard: This class contains problems that are at least as hard as the hardest problems in NP, but they may not necessarily be decision problems or have solutions that can be verified in polynomial time. NP-hard problems may not be in NP themselves. Unlike NP-complete problems, NP-hard problems do not necessarily have to be in NP or have solutions that can be verified in polynomial time.
5. PSPACE: This class contains problems that can be solved by a deterministic Turing machine using polynomial space. It includes problems that may require exponential time but only polynomial space. In other words, PSPACE represents problems for which the space required to solve them grows polynomially with the size of the input.
6. EXP: This class contains problems that can be solved by a deterministic Turing machine in exponential time. EXP contains many difficult problems, including those that are not known to be in P or NP.
7. BPP: (Bounded-Error Probabilistic Polynomial Time) BPP consists of all decision problems for which there is a probabilistic Turing machine that runs in polynomial time and produces the correct answer with high probability. BPP algorithms may occasionally produce incorrect results, but the probability of error is bounded.

Complexity

The complexity of a computational problem refers to the amount of computational resources (such as time, space, or other resources) required to solve the problem. It is often measured in terms of time complexity, space complexity, or both.

1. Time Complexity: Time complexity measures the amount of time required by an algorithm to solve a problem as a function of the size of the input. It is usually expressed using Big O notation. For example, an algorithm with time complexity O(n²) means that its runtime grows quadratically with the size of the input.
2. Space Complexity: Space complexity measures the amount of memory space required by an algorithm to solve a problem as a function of the size of the input. Like time complexity, it is also typically expressed using Big O notation. An algorithm with space complexity O(n) means that it uses memory space linearly proportional to the size of the input.
3. Other Complexities: Apart from time and space complexity, other resources such as communication complexity (for distributed systems), energy complexity (for energy-efficient algorithms), and more, can also be considered depending on the problem domain.
   Communication complexity deals with the amount of communication required between different components or nodes in a distributed system to solve a given problem.

In distributed computing, where computation is spread across multiple machines or nodes, minimizing the amount of communication can be crucial for reducing latency, bandwidth usage, and overall system efficiency.
Communication complexity is often measured in terms of the number of messages exchanged between nodes, the total amount of data transmitted, or other relevant metrics.
Algorithms with lower communication complexity are generally preferred in distributed systems, as they can lead to better scalability, fault tolerance, and performance.

Energy complexity focuses on the amount of energy consumed by an algorithm or a computational process, particularly in energy-constrained environments such as mobile devices, IoT devices, and battery-powered systems.
In such environments, optimizing energy consumption is essential for prolonging device battery life, reducing operational costs, and minimizing environmental impact.
Energy complexity analysis involves considering factors such as CPU usage, memory access patterns, data transmission/reception, and other activities that contribute to energy consumption.
Energy-efficient algorithms aim to minimize unnecessary computation, reduce idle time, optimize data transmission, and utilize low-power modes effectively.

The Space-Time Tradeoff in Algorithms

The tradeoff involves making decisions about how to balance the use of memory (space) and computational effort (time) to optimize the performance of an algorithm.

• Lookup Tables vs. Calculations: Instead of repeatedly calculating a value based on an input, store those pre-calculated values in a table (space) for faster retrieval (time).
• Caching: Caching frequently accessed data in memory (space) reduces the need to re-compute or fetch it from slower storage (time) for subsequent requests.
• In-place vs. Out-of-place Sorting: Some sorting algorithms like bubble sort can modify the original input array (in-place) using less space, but might be slower. Other algorithms like merge sort require extra space for temporary arrays (out-of-place) but can be faster.

The optimal balance between space and time complexity depends on various factors such as the characteristics of the problem, the available resources (memory, processing power), and the specific requirements of the application.

Finding the Sweet Spot:

• Hardware Constraints: If memory is limited, a space-efficient algorithm might be preferred even if it’s slower.
• Input Size: For very large inputs, the time penalty of a space-intensive algorithm might outweigh the benefits.
• Frequency of Execution: If the algorithm is used frequently, the time saved by a space-efficient approach might accumulate significantly over time.

Calculation of Time Complexity

The RAM Model
The random access model (RAM) of computation was devised by John von Neumann to study algorithms.

Key Assumptions:

• The RAM has unlimited memory, and each memory access takes one time step.
• Basic operations like arithmetic (+, -, *, /), comparisons (>, <, ==), assignments (=), and control flow statements (if, goto, loop) also take one time step each.
• Subroutines and loops are treated as sequences of these basic operations.

Counting Steps:

To determine the time complexity of an algorithm in the RAM model, count the total number of basic operations the algorithm performs as a function of the input size (n). This essentially translates to counting the number of steps the algorithm takes to execute on an input of size n.

def nested_loop(n, m):
    for i in range(n):
        for j in range(m):
            # sequence of statements
            pass

n = 5
m = 3
nested_loop(n, m)

The outer loop executes n times.
Every time the outer loop executes, the inner loop iterates m times for each iteration of the outer loop.
Total operations for the inner loop for each iteration of the outer loop is m*n times. Thus the time complexity is O(mn) times.
If the j loop is modifed to execute n times (j<n) , insted of m times, then the total time complexity of nested loop is O(n²).

Order of Increasing time complexity:
O(1) < O(log(n)) < O(n log(n)) < O(n² ) < O(n³ ), … , O(2^n )

Calculation of Space Complexity

Space complexity is the amount of memory space that an algorithm or a problem takes during its execution.
The space complexity considers the space used by the variables in the algorithm and the space for input values.

Auxiliary space is the space required by an algorithm during its execution of that algorithm. It is not equal to the space complexity.
Space complexity is the combination or sum of the auxiliary space and the space used by input values.
Space Complexity = Auxiliary Space + Space used by input values

def array_sum(arr):
    total = 0
    for num in arr:
        total += num
    return total

input_array = [1, 2, 3, 4, 5]
result = array_sum(input_array)
print(result)

• Auxiliary Space: The algorithm uses a constant amount of extra memory regardless of the input size. The variables total and num are the main contributors here. Therefore, the auxiliary space is O(1), indicating constant space usage.
• Space Used for Input Values: The input array input_array takes up space proportional to the number of elements in the array (N). Therefore, the space used for input values is O(N), where N is the input size.

So, the overall space complexity of the array_sum algorithm is the sum of the auxiliary space and the space used for input values:

Space Complexity = O(1) (Auxiliary Space) + O(N) (Space Used for Input Values) => O(N)