Algorithm: Time Complexity and Space Complexity

Algorithms are specific sets of instructions given in a particular order to perform a task that is called an algorithm. Algorithms are necessary for solving complex problems efficiently and effectively. They help to automate processes and make them more reliable, faster, and easier to perform. Algorithm complexity provides a way to analyze and compare algorithms based on their performance.

There are two types of complexity in algorithm.

1) Time Complexity

2) Space Complexity

Time Complexity: -

Time taken by the algorithm to complete the task is called the time complexity. Time complexity depends on the size of the input. Algorithm requires the different amount of time based on the input size to complete the task.

We need to consider the number of times the instructions are executed. Based on the founding, we can measure the time-complexity of given algorithm.

a) Best Time Complexity (Omega notation)

b) Average Time Complexity (Theta notation)

c) Worst Time Complexity (Big-o notation)

There are different types of time complexities used:

1. Constant time – O (1)

2. Linear time – O (n)

3. Logarithmic time – O (log n)

4. Quadratic time – O (n^2)

5. Cubic time – O (n^3)

Space Complexity: -

Space complexity measures the amount of memory an algorithm uses as a function of the input size. Like time complexity, it's also expressed using Big O notation.

Common Space Complexities: -

1. O(1) Constant Space: The algorithm uses a fixed amount of memory, regardless of input size.

2. O(n) Linear Space: The memory usage increases linearly with the input size.

3. O(n^2) Quadratic Space: The memory usage grows quadratically with the input size, often seen in algorithms involving nested data structures.