Design and Analysis of Algorithm

4.  Calculate time complexity and space complexity of GCD and TOC problems and implement it.

Solⁿ:

i.    Problem behind the GCD can be given as:

Pseudocode for GCD:

      gcd(x,y)

      while x!=y do

      if x>y

      x=x-y

      else

      y=y-x

      loop

      return x

     

Time Complexity:

                        The time to execute one iteration of the loop depends on whether m>n or not, but both cases take constant time:

Ø      One test,

Ø      a subtraction

Ø      One assignment.

So the time taken for one iteration of the loop is bounded by a constant.

If m=n, there is just one iteration which is referred as   the best-case.
If n=1, there are m iterations; this is the worst-case (and similarly if m=1 there are n iterations).
 The answer found is O((log m)(log n)).

ii.    Problem behind the TOC problem and some of it's rules to solve the problem can be given as:

 There are 3 pegs 'from' , 'using ' and 'to'. Some disks of different sizes are given which can slide onto any peg . Initially all of those are in 'from' peg in order of size with largest disk at the bottom and smallest disk at the top. We have to move all the disks from 'from' peg to 'to' peg . At the end ,'to' peg will have disks in the same order of size . there are some rules :

1)only one disk can be moved from one peg to another peg at a time.

2) A disk can be placed only on top of a larger one .

3) A disk can be moved from top only.

Time Complexity :

Let the time required for n disks is T(n) .

There are 2 recursive call for n-1 disks and one constant time operation to move a disk from 'from' peg to 'to' peg . Let it be k_1.

Therefore,

T(n) = 2 T(n-1) + k₁

T(0) = k₂ , a constant.

T(1) = 2 k₂ + k₁

T(2) = 4 k₂ + 2k₁ + k₁

T(2) = 8 k₂ + 4k₁ + 2k₁ + k₁

Coefficient of k₁ =2ⁿ

Coefficient of k₂ =2ⁿ-1

Time complexity is O(2ⁿ) or O(aⁿ) where a is a constant greater than 1.

So it has exponential time complexity. For single increase in problem size the time required is double the previous one. This is computationally very expensive. Most of the recursive programs takes exponential time that is why it is very hard to write them iteratively .

Space Complexity:

Space for parameter for each call is independent of n i.e., constant. Let it be k .

When we do the 2^nd recursive call 1^st recursive call is over . So, we can reuse the space of 1^st call for 2^nd call . Hence ,

T(n) = T(n-1) + k

T(0) = k

T(1) = 2k

T(2) = 3k

T(3) = 4k

So the space complexity is O(n).

Here time complexity is exponential but space complexity is linear . Often there is a tradeoff between time and space complexity .