- 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 ...

Start Free Trial

No credit card required