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.