O'Reilly logo

Design and analysis of Algorithms, 2nd Edition by Himanshu B Dave

Stay ahead with the world's most comprehensive technology and business learning platform.

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

Start Free Trial

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.

Start Free Trial

No credit card required