Understanding time complexity of algorithms

1. Constant Time Complexity - O(1)
Accessing element at a particular index in an array.

For an array Array, accessing element at index = Array[index] is a constant time operation. 

2. Logarithmic time complexity - O(logn)

Binary search for an element in a sorted array.

For a sorted array find the position of an element using binary search. The algorithm eliminates half of the array under consideration in every iteration. The total number of iterations comes to ~log2(n), for array of size n.   

3. Linear time complexity - O(n)

Find maximum element in an array.

Iterate through the array and store the maximum element present. 

4. Linearithmic time complexity - O(nlogn)

Merge sort of an array.

Use of divide and conquer to sort the array. It has 2 steps, merging and sorting. Merging 'n' elements take O(n). Divide and conquer takes 2T(n/2) time. Using master theorem, it comes to nlogn. 

5. Quadratic time complexity - O(n^2)

Generate all subarrays of an array. 

2 nested loops are required to generate all subarrays of an array of size n.

for (i=0;i<n;i++) // starting point of subarray

{    for(int j=i;j<n;j++) // ending point of subarray

     {

     }

}

6. Exponential time complexity - O(2^n)

Generate all subsequences an an array. 

Recursion can be used to generate all sub-sequences. Visit every index of the array and take a call to either include or not include the particular element into a sub sequence. 

7. Square root time complexity - O(sqrt(n))

Check if a number is prime. 

For a non-prime number since there is at least one factor lesser than or equal to sqrt(n), we iterate from 2 to sqrt(n) to decide the primality. 

8. Factorial time complexity - O(n!)

Get factorial of a number. 

n!=n*(n-1)*(n-2)...2*1. Recursive call to multiply all numbers from n to 1, takes n! time. 

9. Amortized constant time complexity - O(1)

Insertion and access from hash set. 

In general, insertion and accessing from a hash set takes constant time. This is however average TC, meaning in worst case if all elements point to same hash bucket, the TC can be as high as n. 

We will explore more uncommon Time complexity in next episode. 

Connect with me at https://www.preplaced.in/profile/nishchal-manjanbail for mentorship sessions.