Time and Space Complexity in Data Structures

Time complexity is the measurement of the time taken by an algorithm to execute its code based on the input size.

The amount of memory space required by an algorithm during its execution, including the fixed part needed to store data & variables that are not dependent on the problem size.

1. Big O(expression)- It is used to analyze the worst-case time complexity of an algorithm by evaluating the growth rate of a set of functions with respect to the expression.

2. Omega(expression)- It defines the best-case time complexity of an algorithm by examining the growth rate of a set of functions with respect to the expression.

3. Theta(expression)- It analyzes the average-case time complexity of an algorithm by analyzing if a set of functions lies between upper & lower bounds defined by Big O(expression) & Omega(expression).

1. Insertion Sort Best Case- Ω(n) Worst Case- O(n^2) Space Complexity- O(1)

2. Merge Sort Best Case- Ω(nlogn) Worst Case- O(nlogn) Space Complexity- O(n)

1. Linear Search Best Case- Ω(1) Worst Case- O(n) Space Complexity- O(1)

2. Binary Search Best Case- Ω(1) Worst Case- O(log n) Space Complexity- O(1)

Want to take your programming skills to the next level?

Step Up Your Game with InterviewBit Web Stories