C What is BigO analysis What role does it play in data stru

C++

- What is Big-O analysis? What role does it play in data structures? Give an example.

- What is order of magnitude? What role does it play in Big-O analysis?

- Describe each of the following. Give a real world example of three of them:

O(log₂N)

O(N)

O(N log₂N)

O(N²)

O(N³)

O(2^N)

Solution

Big O value of a function represents the limiting behaviour or upper bound when the arguement of the function tends to large value or even infinity. This helps determining the upper bound for the running time of different alogirthms. For example finding a number in an array can be done in a single iteration of the array, so if the size of the array is n then the total run time will be O(n).The actual runtime will be c*n+d. Where c and d are constants.

Order of magnitude means the most computationally expensive part. Suppose if the total run time is n^2+n, then we consider n^2 as it is more computationally expensive in both of them. So this is written as O(n^2)

Examples:

O(logN) --> Binary search

O(NlogN) --> Merge sort

O(N^3) --> Matrix multiplication