Omega Time complexity

Why Master method ? - Master method helps us analysing algorithms with their running time. So, lets consider the integer multiplication - here. Now we get equation 1. The way we reason about recursive algorithm like these is with the help of recurrence. Recurrences What is recurrence? T(n) = max number of operations this algorithm needs to multiply 2 n digit numbers. Recurrence is to express T(n) in terms of recursive calls. [Read More]

a) if statement - O(n) [Omega times n] b) for loop - O(n) [Omega times n] c) for loop with a for loop - O(n*n) [Omega times n squared] d) for loop within a if loop, this if loop is within a for loop - O(n + n*n) [n plus n squared omega] e) while loop - O(n) [Omega times n] f) MergeSort - O(nlogn) [Omega n time logarithmic n] [Read More]