Reference no: EM13188929

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.