Algorithm

Algorithm:
an algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. An algorithm is thus a sequence of computational steps that transform the input into the output .
Pseudocode conventions
We use the following conventions in our pseudocode:
1-Indentation indicates block structure with statement with loop
and conditional statements like(while-do , for-do and if-then-
else). We could also use indicators of block structure begin ,end
statements .
2-The looping constructs while, for, and repeat and the conditional
constructs if, then, and else have interpretations similar to those
in Pascal
3-The symbol "/*" or "//" indicates that the remainder of the line is
a comment.
4-A multiple assignment of the form i ? j ?e (or i = j = e )assigns
to both variables i and j the value of expression e; it should be
treated as equivalent to the assignment j ? e followed by the
assignment i? j.
5-Variables (such as i, j, and key) are local to the given procedure.
We shall not use global variables without explicit indication.
6-Array elements are accessed by specifying the array name
followed by the index in square brackets. For example, A[i]
indicates the ith element of the array A.
7-Compound data are typically organized into objects, which are
composed of attributes or fields. To specify the number of
elements in an array A, we write length[A]. Sometimes, a
pointer will refer to no object at all. In this case, we give it the
special value NIL
8-Parameters are passed to a procedure by value: the called
procedure receives its own copy of the parameters, and if it
assigns a value to a parameter, the change is not seen by the
calling procedure .
9-The Boolean operators "and" and "or" are short circuiting. That
is, when we evaluate the expression "x and y" we first evaluate
x. If x evaluates to FALSE, then the entire expression cannot
evaluate to TRUE, and so we do not evaluate y.







Analysis Basic
There are many algorithms that can solve a given problem. They will have different characteristics that will determine how efficiently each will operate.
When we analyze an algorithm, we first have to show that the algorithm does properly solve the problem because if it doesn’t, its efficiency is not important. Next, we look at how efficiently it solves the problem.
Analyzing an algorithm determines the amount of “time” that algorithm takes to execute. The number of operations is related to the execution time, so we will sometimes use the word time to describe an algorithm’s computational complexity.
In a very general sense, algorithms can be classified as either repetitive or recursive.
Repetitive algorithms have loops and conditional statements as their basis, and so their analysis will entail determining the work done in the loop and how many times the loop executes.
Recursive algorithms solve a large problem by breaking it into pieces and then applying the algorithm to each of the pieces.
These are sometimes called divide and conquer algorithms and provide a great deal of power in solving problems.

What to count and consider?
There are two classes of operations that are typically chosen for the significant operation: comparison or arithmetic.
Cases to consider
Choosing what input to consider when analyzing an algorithm can have a significant impact on how an algorithm will perform.
If the input list is already sorted, some sorting algorithms will perform very well, but other sorting algorithms may perform very poorly . The opposite may be true if the list is randomly arranged instead of sorted.
Best Case
As its name indicates, the best case for an algorithm is the input that requires the algorithm to take the shortest time.
If we are looking at a searching algorithm, the best case would be if the value we are searching for (commonly called the target or key) was the value stored in the first location that the search algorithm would check. This would then require only one
comparison no matter how complex the algorithm is .



Worst Case
Worst case is an important analysis because it gives us an idea of the most time an algorithm will ever take. Worst-case analysis requires that we identify the input values that cause an algorithm to do the most work.
For searching algorithms, the worst case is one where the value is in the last place we check or is not in the list. This could involve comparing the key to each list value for a total of N comparisons .
Average Case
The basic process begins by determining the number of different
groups into which all possible input sets can be divided. The second step is to determine the probability that the input will come from each of these groups.
The third step is to determine how long the algorithm will run for each of these groups. All of the input in each group should take the same amount of time, and if they do not, the group must be split into two separate groups. When all of this has been done, the average case time is given by the following formula:



Where n is the size of the input, m is the number of groups, pi is the probability that the input will be from group i, and ti is the time that the algorithm takes for input from group i.