master-method

Normal Integer method If we consider the integer multiplication, we need 2 integers and output is also integer. Suppose we have to multiply 5678*1234. In the normal way, we will realize following: 5678 X 1234 \------------ 22712 //first number multiply as is i.e. 4\*5678 17034- //2nd time, shift (left) and then multiply the number as 3\*5678 11356-- //shift twice 5678--- //shift thrice \------------ 7006652 ```So, each time we multiply, depending on the digit of the 2nd number, we shift and then multiply. [Read More]

After establishing what the running time of an algorithm based on three variables a, b, d, we might be wondering what is the meaning behind this method. Where do these logs and exponents come from? If we look at the amount of work done at a single level of the recursion tree, we get that it is, where aj is the number of level-j subproblems and the rest is the amount of work per level-j subproblem. [Read More]

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]

Recurrence Relations Recurrence relations often arise in calculating the time and space complexity of algorithms. The amount of time (or space) that a program takes, Tk, is typically a function of the size, k, of the input data. A recurrence relation arises when Tk is some function of Tk’ for k’ Logarithmic Complexity The following recurrence **Tk = Tk/2 + a if k!=1 = b if k=1 ** has the solution [Read More]