2. (8 points) Find the tightest upper bound time and space complexity for each of the...

 

Transcribed Image Text:

2. (8 points) Find the tightest upper bound time and space complexity for each of the following code snippets (a) (4 points) Assume the size of the vector arr is N Do not assume any code optimization by the compiler. bool search (vector & arr, int s, int e, int x) { if (s >e) return false; int m (se) / 2; if (arr[m] x) return true; else if (arr[m]>x) return search (arr, s, m- 1, x); else return search (arr, m + 1, e, x); bool search (vector arr, int x) ( return search (arr, 0, arr.size() - 1, x); (b) (4 points) Assume the size of the vector v is N void swap (vector &v) { int i=0; int jv.size()-1; while (j>i) { swap (v[i++],v[j--]); 2. (8 points) Find the tightest upper bound time and space complexity for each of the following code snippets (a) (4 points) Assume the size of the vector arr is N Do not assume any code optimization by the compiler. bool search (vector & arr, int s, int e, int x) { if (s >e) return false; int m (se) / 2; if (arr[m] x) return true; else if (arr[m]>x) return search (arr, s, m- 1, x); else return search (arr, m + 1, e, x); bool search (vector arr, int x) ( return search (arr, 0, arr.size() - 1, x); (b) (4 points) Assume the size of the vector v is N void swap (vector &v) { int i=0; int jv.size()-1; while (j>i) { swap (v[i++],v[j--]);