Difference between revisions of "Chapter 2"

From The Algorithm Design Manual Solution Wiki
Jump to navigation Jump to search
Line 1: Line 1:
 
Problems
 
Problems
  
:[[2.1]]
+
:[[2.1]]. What value is returned by the following function? Express your answer as a function of <math>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)
 +
 
 +
[[2.1|Solution]]
 +
 
  
 
:2.2
 
:2.2

Revision as of 17:53, 3 September 2020

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