Design and Analysis of Algorithms, 2nd Edition by Pearson

D.2.8  Chapter 14: Efficiency of Algorithms

1. Given an arbitrary integer n and an arbitrary integer-valued function f(n), give an algorithm that has space complexity f(n) and time complexity f(n) for an input of size n.

   Solution This algorithm does not need to do anything meaningful. For example, it can be the one that simply “eats” the desired time and space as follows:

   Algorithm D.37 | TrivialAlgorithm(n)

    

   1	K = f(n);
   2	Allocate an array A of size K;
   3	for i = 1 to K do
   4	A[i] = 0;
   5	end

   Note. Here it is assumed that f(n) is computable and takes some constant time to compute.

2. Explain some key diffierences between average analysis and amortized analysis of algorithms.

   Solution There are two key diffierences between them. The first ...