Time complexity

Document Preview:

Question 1a: For n ? 0 , what is the time complexity of the method q(1, n). Show the details of your calculation of O(q(1, n) ˜ O(?). public int q (int i, int n) { return i+(i >= n ? 0 : q(i+i, n)); } Answer: Linear time. O(n) Question 1b: For n ? 0 , what is the time complexity of the r(n) method. Show the details of you calculation of O(r(n)) ˜ O(?). public int r(int n) { int sum = 0; for (int i=1; i <= n+n; i++) sum+=i + q(1,n); return sum; } Answer: Linear time. O(n) Question 1c: For n ? 0 , what is the time complexity of the algorithm_1(int n) method. Show the details of you calculation of O(algorithm_1(n)) ˜ O(?). public void algorithm_1(int n) { if (n < 1) return; System.out.println(q(1, n)*n); System.out.println(r(n)); System.out.println(q(1, n+n) + r(n+n)); } Answer: Linear time. O(n) Bonus:- public int t(int n) { for (int i=1; i <= n+n; i++) { for (int j=1; j < i; j++) sum+=i + q(1,n); } Answer: Quadratic time. O(n^2) Question 2: n ? 0 , what is the time complexity of the binarySearch(array[n], key) algorithm. Show the details of you calculation of O(binarySearch(array[n], key)) ˜ O(?). time = O(log n) 2^t -1 = n 2^t = n + 1 log2(2^t) = log2(n+1) t = log2 n + 1 The time is logarithmic in the number of elements. Or proportional to the logarithm of # of elements.