**Divide**the problem into a number of subproblems**Conquer**the subproblems by solving them recursively. If the subproblem sizes are small enough, however, just solve the subproblems in a straightforward manner**Combine**the solutions to the subproblems into the solution for the original problem**Divide:**Divide the*n*-element sequence to be sorted into two subsequences of*n*/2 elements each**Conquer:**Sort the two subsequences recursively using merge sort**Combine:**Merge the two sorted subsequences to produce the sorted answer

** Analyzing **an algorithm has come to mean predicting the resources that the algorithm requires model analyses are usually excellent predictors of performance on actual machines.

Analyzing even a simple algorithm in the RAM model can be a challenge. The mathematical tools required may include combinatorics, probability theory, algebraic dexterity, and the ability to identify the most significant terms in a formula. Because the behavior of an algorithm may be different for each possible input

The time taken by the INSERTION-SORT procedure depends on the input: sorting a thousand numbers takes longer than sorting three numbers. Moreover, INSERTION-SORT can take different amounts of time to sort two input sequences of the same size depending on how nearly sorted they already are. In general, the time taken by an algorithm grows with the size of the input, so it is traditional

The best notion for ** input size **depends on the problem being studied. For many problems

The ** running time **of an algorithm on a particular input is the number of primitive operations or "steps" executed

A constant amount of time is required to execute each line of our pseudocode. One line may take a different amount of time than another line, but we shall assume that each execution of the *i*th line takes time *ci *, where *ci *is a constant

When a **for **or **while **loop exits in the usual way (i.e., due to the test in the loop header), the test is executed one time more than the loop body. We assume that comments are not executable statements, and so they take no time

we separate the process of ** calling **the subroutine-passing parameters to it, etc.-from the process of

**the subroutine Insertion sort uses an**

*executing***approach**

*incremental*One advantage of divide-and-conquer algorithms is that their running times are often easily determined using techniques that will be introduced in Chapter 4

Many useful algorithms are ** recursive **in structure: to solve a given problem, they call themselves recursively one or more times to deal with closely related subproblems. These algorithms typically follow a

**approach: they break the problem into several subproblems that are similar to the original problem but smaller in size, solve the subproblems recursively, and then combine these solutions to create a solution to the original problem**

*divide-and-conquer*The divide-and-conquer paradigm involves three steps at each level of the recursion:

The ** merge sort **algorithm closely follows the divide-and-conquer paradigm. Intuitively, it operates as follows:

The key operation of the merge sort algorithm is the merging of two sorted sequences in the

"combine" step. To perform the merging, we use an auxiliary procedure MERGE(*A*, *p*, *q*, *r*),

where *A *is an array and *p*, *q*, and *r *are indices numbering elements of the array such that *p *≤ *q *< *r*. The procedure assumes that the subarrays *A*[*pà q*] and *A*[*q *+ 1 à *r*] are in sorted order. It ** merges **them to form a single sorted subarray that replaces the current subarray

*A*[

*p à r*]

Merge Sort has: Time Θ(*n*), where n = r – p + 1( is the number of elements being Merged)* *When an algorithm contains a recursive call to itself, its running time can often be described by a ** recurrence equation **or

**, which describes the overall running time on a problem of size**

*recurrence**n*in terms of the running time on smaller inputs. We can then use mathematical tools to solve the recurrence and provide bounds on the performance of the algorithm

[…] Analyzing Algorithms « Abdelrahman Al-Ogail's Blog […]