Difference between revisions of "Chapter 2"

From The Algorithm Design Manual Solution Wiki
Jump to navigation Jump to search
Line 1: Line 1:
Problems
+
=Algorithm Analysis=
 +
 
 +
===Program Analysis===
  
 
:[[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.
 
:[[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.
Line 24: Line 26:
  
 
:2.7
 
:2.7
 +
 +
 +
===Big Oh===
 +
  
 
:2.8
 
:2.8
Line 82: Line 88:
  
 
:2.36
 
:2.36
 +
 +
===Summations===
 +
  
 
:2.37
 
:2.37
Line 96: Line 105:
  
 
:2.43
 
:2.43
 +
 +
===Logartihms===
 +
  
 
:2.44
 
:2.44
Line 104: Line 116:
  
 
:2.47
 
:2.47
 +
 +
===Interview Problems===
 +
  
 
:2.48
 
:2.48

Revision as of 17:57, 3 September 2020

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.
  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