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:
  1. Will it correctly sort an unsorted list of items? In other words: does it work?
  2. Does it meet the definition of an algorithm? If not, why not.

    If you answered yes to the previous questions, then answer:
  3. Is the proposed algorithm tractable to compute?
  4. 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.