Chapter 2

Algorithm Analysis

Program Analysis

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

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