# Chapter 2

## Contents

# Algorithm Analysis

### Program Analysis

- 2.1. What value is returned by the following function? Express your answer as a function of . Give the worst-case running time using the Big Oh notation.

mystery(n) r:=0fori:=1ton-1doforj:=i+1tondofork:=1tojdor:=r+1return(r)

- 2.2. What value is returned by the following function? Express your answer as a function of . Give the worst-case running time using Big Oh notation.

pesky(n) r:=0fori:=1tondoforj:=1toidofork:=jtoi+jdor:=r+1 return(r)

- 2.3. What value is returned by the following function? Express your answer as a function of . Give the worst-case running time using Big Oh notation.

prestiferous(n) r:=0fori:=1tondoforj:=1toidofork:=jtoi+jdoforl:=1toi+j-kdor:=r+1 return(r)

- 2.4. What value is returned by the following function? Express your answer as a function of . Give the worst-case running time using Big Oh notation.

conundrum()fortodofortodofortodoreturn()

- 2.6. Suppose the following algorithm is used to evaluate the polynomial

for to do end

- How many multiplications are done in the worst-case? How many additions?
- How many multiplications are done on the average?
- Can you improve this algorithm?

- 2.7. Prove that the following algorithm for computing the maximum value in an array is correct.

max(A)fortondoifthenreturn(m)

### Big Oh

- 2.8

- 2.9

- 2.10

- 2.11

- 2.12

- 2.13

- 2.14

- 2.15

- 2.16

- 2.17

- 2.18

- 2.19

- 2.20

- 2.21

- 2.22

- 2.23

- 2.24

- 2.25

- 2.26

- 2.27

- 2.28

- 2.29

- 2.30

- 2.31

- 2.32

- 2.33

- 2.34

- 2.35

- 2.36

### Summations

- 2.37

- 2.38

- 2.39

- 2.40

- 2.41

- 2.42

- 2.43

### Logartihms

- 2.44

- 2.45

- 2.46

- 2.47

### Interview Problems

- 2.48

- 2.49

- 2.50

- 2.51

- 2.52

- 2.53

- 2.54

- 2.55

Back to Chapter List