Define various terms such as algorithm, various approaches to design an algorithm, time complexity, space complexity, best case, average case and worst-case time complexity etc.

Algorithm

In mathematics and computer science, an algorithm is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing calculations and data processing.

Approaches to design an algorithm

  • Top-Down Approach
  • Bottom-up approach
Top-Down Approach: In the top-down approach, a large problem is divided into small sub-problem. and keep repeating the process of decomposing problems until the complex problem is solved.

Bottom-up approach: The bottom-up approach is also known as the reverse of top-down approaches.
In approach different, part of a complex program is solved using a programming language and then this is combined into a complete program.

Time complexity

The time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the input. Note that the time to run is a function of the length of the input and not the actual execution time of the machine on which the algorithm is running on.

Space complexity

The space complexity of an algorithm quantifies the amount of space taken by an algorithm to run as a function of the length of the input.

Worst Case Analysis

In the worst-case analysis, we calculate the upper bound on the running time of an algorithm. It is the maximum time taken by an algorithm to solve a problem.

Best Case Analysis

In the best case analysis, we calculate the lower bound on the running time of an algorithm. It is the minimum time taken by an algorithm to solve a problem.

Average Case Analysis 

In average case analysis, we take all possible inputs and calculate the computing time for all of the inputs. It is in between best case and worst case. Means the average time taken by an algorithm to solve a problem.