Answers to tutorial exercises from chapter 2

2.1: 3: yes; 7a: 8; 7b: 10; 9a: same; 9c: same; 9e: same. 2.2: 1a: Θ(n); 1b: Θ(1); 1c: Θ(n); 3a: Θ(n^20); 3b: Θ(n); 3c: Θ(n^2 log n); 3d: Θ(3^n); 3e: Θ(log n); 7a: true; 7b: true; 7c: true; 7d: false; 9a: Θ(n log n); 9b: Θ(n). 2.3: 1b: 2046; 1d: (n^2+3n-4)/2; 1f: (3^(n+2)-9)/2; 2a: Θ(n^5); 2c: Θ(n2^n); 4a: Σ(i=1..n)i^2; 4b: multiplication; 4c: n; 4d: Θ(2^b); 4e: Θ(1). 2.4: 1b: 4.3^(n-1); 1d: 2n-1; 4a: Q(n) = n^2; 4b: M(n)=n-1; 4c: C(n)=3(n-1) [NB 2(n-1) also ok)].