**Time Complexity **

The **time complexity** of an algorithm is basically the running time of a program as a function of the input size

**Space Complexity**

**Space complexity** of an algorithm is the amount of computer memory that is required during the program execution as a function of the input size

In other words, the number of machine instructions which a program executes is called its **time complexity**. This number is primarily dependent on the size of the program’s input and the algorithm used

Generally, the space needed by a program depends on the following two parts:

- Fixed part: It varies from problem to problem. It includes the space needed for storing instructions, constants, variables, and structured variables (like arrays and structures).
- Variable part: It varies from program to program. It includes the space needed for recursion stack, and for structured variables that are allocated space dynamically during the runtime of a program

**Worst-case, Average-case, Best-case, and Amortized Time Complexity**

**Worst-case running time**

This denotes the behaviour of an algorithm with respect to the worst possible case of the input instance. The **worst-case running time** of an algorithm is an upper bound on the running time for any input. Therefore, having the knowledge of worst-case running time gives us an assurance that the algorithm will never go beyond this time limit

**Average-case running time**

The **average-case running** time of an algorithm is an estimate of the running time for an ‘average’ input. It specifies the expected behaviour of the algorithm when the input is randomly drawn from a given distribution. Average-case running time assumes that all inputs of a given size are equally likely

**Best-case running time**

The term ‘best-case performance’ is used to analyse an algorithm under optimal conditions. For example, the best case for a simple linear search on an array occurs when the desired element is the first in the list. However, while developing and choosing an algorithm to solve a problem, we hardly base our decision on the best-case performance. It is always recommended to improve the average performance and the worst-case performance of an algorithm.

**Amortized running time**

Amortized running time refers to the time required to perform a sequence of (related) operations averaged over all the operations performed. Amortized analysis guarantees the average performance of each operation in the worst case