#### D.2.8 Chapter 14: Efficiency of Algorithms

- 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. - Explain some key diffierences between average analysis and amortized analysis of algorithms.
**Solution**There are two key diffierences between them. The first ...

Get *Design and analysis of Algorithms, 2nd Edition* now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.