# Difference between revisions of "Chapter 2"

Jump to navigation
Jump to search

Line 55: | Line 55: | ||

<math>x = 2x</math> | <math>x = 2x</math> | ||

:Let <math>f(n)</math> be the complexity of this algorithm (or equivalently the number of times * is printed). Proivde correct bounds for <math> O(f(n))</math>, and <math>/Theta(f(n))</math>, ideally converging on <math>\Theta(f(n))</math>. | :Let <math>f(n)</math> be the complexity of this algorithm (or equivalently the number of times * is printed). Proivde correct bounds for <math> O(f(n))</math>, and <math>/Theta(f(n))</math>, ideally converging on <math>\Theta(f(n))</math>. | ||

+ | |||

+ | [[2.5|Solution]] | ||

## Revision as of 19:35, 3 September 2020

## 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+1return(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+1return(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(r)

- 2.5. Consider the following algorithm: (the print operation prints a single asterisk; the operation doubles the value of the variable ).

fortowhile():

- Let be the complexity of this algorithm (or equivalently the number of times * is printed). Proivde correct bounds for , and , ideally converging on .

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

for to do

- 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. True or False?

- Is ?
- Is ?

- 2.9. For each of the following pairs of functions, either is in , is in , or . Determine which relationship is correct and briefly explain why.

- ; +
- ;
- ;
- ;
- ;
- ;
- ;
- ;

- 2.10. For each of the following pairs of functions and , determine whether , , or both.

- ,
- ,
- ,
- ,
- ,
- ,

- 2.11. For each of the following functions, which of the following asymptotic bounds hold for ?

- 2.12. Prove that .

- 2.13. Prove that .

- 2.14. Prove or disprove: <math>\Theta(n^2) = \Theta(n^2+1)<\math>.

- 2.16

- 2.18

- 2.20

- 2.22

- 2.24

- 2.26

- 2.28

- 2.30

- 2.32

- 2.34

- 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