Question

(a) A robot moves on a NxN grid, starting in the top-left comer S and moving either right or down at each step, until destination D is reached. Determine the "big O" complexity of a program that prints all possible paths from S to D. (b) Let A[1 ..n] be an array of bits (1 or 0) and F() a function of time complexity theta(n). Give the time complexity of the following C++ code fragment. Justify your result by considering different cases for A. counter = 0;for (i = 1;i < = n;i++) { if (A[i] == 1) counter++; else{ F(counter);counter = 0;} }

data structure

Answer 1

Question 4 a)

A path from S to D will contain N-1 right moves and N-1 down moves. So, number of paths from S to D is equal to number of ways of arranging N-1 right moves and N-1 down moves

So, there are $\frac{(N-1 &plus; N-1)!}{(N-1)!(N-1)!}$ possible paths from S to D.

So time complexity to print all the possible paths = $O(\frac{(N-1 &plus; N-1)!}{(N-1)!(N-1)!})$

Question 4 b)

Let m = number of zeros in array A.

So, Time complexity of given code = (m)*$\theta$(n) + (n-m)*(1)

= $\theta$(nm)