Time Complexity
Time complexity vs No. of iterations Time complexity --> how algorithm scales with data (means for very large n) Eg.- N² v/s 1000*n ==> for small n --> N² is better but very negligible difference But for large n ---> huge difference (seconds v/s hours) Big Oh - supremum (worst case) Big Omega - infimum ( best case) Big Theta - lies in range [infimum,supremum] => Gives clear picture of time average cas e = > O({∑all possible time}/ total number of possibilities) Amortized / Average time complexity When we insert element into vector using push_back => two scenarios can occur: The array has room for the new element => O(1) The array is full => resized to make room for the new element. This involves creating a new array of 2*size, copying the elements from the old array to the new one, and then adding the new element. This operation has a time complexity of O(n) in C++11 => elements are moved inst...