Analyzing Algorithms

    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 ith 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 executing the subroutine  Insertion sort uses an incremental approach

    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 divide-and-conquer 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

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

    • 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

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

    • 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

    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 recurrence, which describes the overall running time on a problem of size 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

One thought on “Analyzing Algorithms

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s