With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required