## Algorithms Exercise, Part I

What is the Big-O running time of the following two functions?
function method1(array)
{
var prod = 1;
var indx = 0;
for(var i = 0; i < array.length; i = i + 4)
prod = prod * array[i];
return prod;
}
function method2(array)
{
indx = array.length - 1
prod = 1;
for (var i = array.length - 1; i > 0; i = Math.floor(i / 2))
prod = prod * array[i];
return prod;
}

## Algorithms Exercise, Part II

Consider the following definition of an algorithm:
An *algorithm* is a sequence of unambiguous instructions for
solving a problem, i.e., for obtaining a required output for any
legitimate input in a finite amount of time.

(From __Introduction to the Design and Analysis of Algorithms, 2nd Edition__, Anany Levitin, 2007.)

Described below are three different proposals for sorting algorithms:
Fast Bubble Sort, Modified Merge Sort, and Permutation Sort.
For each one, answer the following questions:
- Will it correctly sort an unsorted list of items? In other words: does it work?
- Does it meet the definition of an algorithm? If not, why not.

If you answered yes to the previous questions, then answer:
- Is the proposed algorithm tractable to compute?
- Take a stab at figuring out the running time in big O notation.

### Fast Bubble Sort

First compare the first and second element in the list, swap them if
they are out of order. Repeat the process for the second and third
elements in the list, and for each successive pair until the end of
the list is reached. Repeat this process until the list is sorted.

### Modified Merge Sort

Sort the first half of the list and the second half of the list
independently. Then merge the two sorted sub-lists according to the
merge procedure described in class.

### Permutation Sort

Assume that we have an efficient^{*} method for generating all
permutations of the items that we wish to sort. A permutation is an
ordering of the items; our method will allow us to generate every
possible ordering. For example, if the items are 5, 3, and 7, this
procedure would allow us to produce the following:

5 3 7

5 7 3

3 5 7

3 7 5

7 5 3

7 3 5

Now consider the following algorithm for finding a sorted version of the
original input among the various permutations:

For each permutation of the items to be sorted, compare each adjacent
pair of items to see whether they are in order. If all pairs are in
order, terminate, and return the sorted list.

* O(1) to produce the next permutation in the sequence from the
previous permutation.