Chapter 2

Problems

2.1. What value is returned by the following function? Express your answer as a function of [math]\displaystyle{ n }[/math]. Give the worst-case running time using the Big Oh notation.

  function mystery(n)
      r:=0
      for i:=1 to n-1 do
          for j:=i+1 to n do
              for k:=1 to j do
                  r:=r+1
       return(r)

Solution

2.2

2.3

2.4

2.5

2.6

2.7

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

2.37

2.38

2.39

2.40

2.41

2.42

2.43

2.44

2.45

2.46

2.47

2.48

2.49

2.50

2.51

2.52

2.53

2.54

2.55

Back to Chapter List