Data structures are how we organize and store data in a computer. The time complexity of a data structure is how long it takes to insert, delete, or find an element in the data structure. The time complexity of a data structure is important to consider when choosing which data structure to use for a particular application.
Types of notations :
- Big Oh Notation
- Omega Notation
- Theta Notation
- O-notation: It is used to denote asymptotic upper bound. For a given function g(n), we denote it by O(g(n)). Pronounced as “big-oh of g of n”. It is also known as worst case time complexity as it denotes the upper bound in which the algorithm terminates.
- Ω-notation: It is used to denote Asymptotic Lower Bound. For a given function g(n), we denote it by Ω(g(n)). Pronounced as “big-omega of g of n”. It is also known as best case time complexity as it denotes the lower bound in which the algorithm terminates.
- 𝚯-notation: It is used to denote the average time of a program.
There are four main data structures:
- Arrays
- Linked Lists
- Stacks
- Queues.
The time complexity of each of these data structures are different.
Best Case
Average Case
Worst Case
What do you mean by "Space Complexity" ?
Space Complexity is a term used in computer science to describe the amount of space required by an algorithm or program to run. It is usually expressed as a function of the input size.
For example, a program that requires O(n) space to run would need n units of space to store its input.
There are two primary factors that affect the space complexity of an algorithm:
- The number of different items that need to be stored and the amount of information that needs to be stored about each item.
- The number of items is usually a function of the size of the input, while the amount of information can be a function of the item’s key, value, or position in the input.
There are a few basic measures of space complexity that are commonly used:
O(1) – Constant space
O(n) – Linear space
O(n logn) – Logarithmic space
O(n2) – Quadratic space
O(n3) – Cubic space
O(2n) – Exponential space
The most common measure is O(n), which describes an algorithm that uses linear space.
For example: int consumes 4 bytes of memory.
