Question

1. Explain: Analysis of algorithms with the example.

2. Explain with example: How computational time of an algorithm depends on

   input size?

3. Write an algorithm (using whatever method you prefer) that takes an input of 10 integers, sorts the integers in ascending order and out puts the sorted list.

4. In relation to computational time of your algorithm for part 4, what arrangement of the input numbers will cause the best case computational time? What arrangement will cause the worst case time?

Answer 1

1)

Analysis of algorithms is the determination of the amount of time and space resources required to execute it. Usually, the efficiency or running time of an algorithm is stated as a function relating the input length to the number of steps, known as time complexity, or volume of memory, known as space complexity.

Example :-

for (int i = 0; i < a.length; i++) {
    System.out.println(a[i]);
}

Here n=a.length (provided we know that all of the items in the array have a fixed size, which is often the case). We have

• 1 initialization of i
• n comparisons of i against a.length
• n increments of i
• n array indexing operations (to compute a[i])
• n invocations of System.out.println

so we write T(n)=4n+1.

All operations are not created equal. The printing completely overwhelms the increments, compares and indexing operations. We might as well talk about having nn compare-index-print-increment operations. Then T(n)=n+1. While we’re at it, we might as well realize that initialization doesn’t mean much, so we’re safe to write T(n)=n.

2)

A “computational problem” is a function whose:

1. Input is a string formed from the elements of a fixed finite set, called the alphabet set.
2. Input Size is the length of a particular input string. For example, if {0,1} is the alphabet set, then the string 001110 is a input of length 6. For any integer n>0 there are 2n possible inputs (the set {0,1}n).
3. Output is a string (usually consisting of elements from the alphabet set, but may also have elements from outside the alphabet set). If the “computational problem” is a “decision problem”, then the output is a one bit string (typically 0/1).

Let f(n) be some function (not to be confused with the function the algorithm is computing) of the input size n (and not the input itself).

For a given algorithm for any computational problem, following are the two important ways of classifying its (worst-case) time complexity.

1. Giving an upper bound : We say an algorithm runs in time O(f(n)), if there is an integer m and a constant c (independent of n), such that for any value of n≥m and for any input of size n, the running time of the algorithm is at most c×f(n).
2. Giving a lower bound : We say an algorithm runs in time Ω(f(n)), if there is a constant c, such that the running time of the algorithm is at least c×f(n), (now this get trickier) for infinitely many inputs, i.e. there can be inputs on which the time taken is less than c×f(n), but the set of inputs on which the time taken is at least c×f(n) must not be finite.

3)

Algorithm Bubble sort

We assume list is an array of 10 elements. We further assume that swap function swaps the values of the given array elements.

begin BubbleSort(list)

   for all elements of list
      if list[i] > list[i+1]
         swap(list[i], list[i+1])
      end if
   end for
   
   return list
   
end BubbleSort

If an array is already in sorted order, and bubble sort makes no swaps, the algorithm can terminate after one pass.O(n) is the best-case running time for bubble sort.  Bubble sort has a worst-case and average complexity of О(n²), where n is the number of items being sorted.