2.3- Math Analysis of Nonrecursive Algorithms

Question 1

1. Decide on a parameter (or parameters) indicating an input’s size.
2. Identify the algorithm’s basic operation. (As a rule, it is located in the innermost loop.)
3. Check whether the number of times the basic operation is executed depends
   only on the size of an input. If it also depends on some additional property,
   the worst-case, average-case, and, if necessary, best-case efficiencies have to
   be investigated separately.
4. Set up a sum expressing the number of times the algorithm’s basic operation
   is executed.
5. Using standard formulas and rules of sum manipulation, either find a closedform formula for the count or, at the very least, establish its order of growth.

Answer 1

Analyzing the time efficiency of nonrecursive algorithms

Question 2

check whether all the
elements in a given array of n elements are distinct. This problem can be solved
by the following straightforward algorithm.

ALGORITHM UniqueElements(A[0..n − 1])

//Determines whether all the elements in a given array are distinct
//Input: An array A[0..n − 1]
//Output: Returns “true” if all the elements in A are distinct
// and “false” otherwise
for i ← 0 to n − 2 do
for j ← i + 1 to n − 1 do
if A[i] = A[j ]return false
return true

Answer 2

element uniqueness problem

Question 3

ALGORITHM Binary(n)
//Input: A positive decimal integer n
//Output: The number of binary digits in n’s binary representation
count ← 1
while n > 1 do
count ← count + 1
n ← [n/2]
retturn count

Answer 3

The following algorithm finds the number of binary digits in the
binary representation of a positive decimal integer.