Going Further on Programming Assignment 5

These questions/problems/tasks allow you to go further on Programming Assignment 5. They are neither required nor for extra credit. They will, however, help you gain a deeper understanding of the material.

1 Algorithm Analysis: The following questions require you to analyze the algorithm you developed to find a single alien.

Given the search order used in your algorithm, what is the worst case (or what are the worst cases)? In other words, "when" will your algorithm require the largest number of iterations to find the alien (where "when" refers to the location of the alien)?
In the worst case, how many iterations will your algorithm take to find the alien, assuming the grid is ?
In the worst case, how many iterations will your algorithm take to find the alien given an arbitrary grid? Your answer must be expressed in terms of . (Hint: This is a difficult question that requires some of what you learned in your discrete mathematics courses. Think about recurrence relations and logarithms.)

2 Algorithmic Thinking: The following questions require you to modify the algorithm you developed for the HeinousAlienLocator.

The management at PIP is concerned that some aliens may be able to clone themselves and, as a result, be in more than one location at a time. Hence, they want you to add a method with the following signature:
```
  public int searchEverywhere(int x, int y, int width)
  
```
that will search the entire grid and return the number of cells that contain an alien (and its clones).
Modify the HeinousAlienLocator so that it works with arbitrary rectangular grids. (Note: Make sure you make a copy of all of your working code before starting.)