Suppose that a doubly linked list is implemented as a class

Suppose that a doubly linked list is implemented as a class DoublyLinkedList that uses sentinel doubly linked nodes header and trailer and no other instance variables. Write a method of the class called remove Middle that removes either the middle node from a list of odd length, or the middle two nodes from a list of even length. The method should throw an exception if the required nodes do not exist. Give a O-estimate for the run time of your method in terms of the number n of elements in the list. Give O-estimate for the run times of the following methods in terms of the parameter called m. At least one of the methods is inefficient, identify this method and give a different implementation that has a significantly better run time (for large values of n). public static int fibonacci (int n) {if (n

Solution

Out of the given 3 methods :
I find (a) fibonacci method is inefficient . Here loops are used so the time complexity is (n-2) but if we use matrix multiplication method we can have time complexity upto (log n) which is very less compare to the given method .

So , the code for finding fibonacci series is :

#include <math>
public static int Fibonacci(int n) {

int num = Math.abs(n);
if (num == 0) {
return 0;
}
else if (num <= 2) {
return 1;
}

int[][] number = { { 1, 1 }, { 1, 0 } };
int[][] result = { { 1, 1 }, { 1, 0 } };

while (num > 0) {
if (num%2 == 1) result = MultiplyMatrix(result, number);
number = MultiplyMatrix(number, number);
num/= 2;
}
return result[1][1]*((n < 0) ? -1:1);
}

public static int[][] MultiplyMatrix(int[][] mat1, int[][] mat2) {
return new int[][] {
{ mat1[0][0]*mat2[0][0] + mat1[0][1]*mat2[1][0],
mat1[0][0]*mat2[0][1] + mat1[0][1]*mat2[1][1] },
{ mat1[1][0]*mat2[0][0] + mat1[1][1]*mat2[1][0],
mat1[1][0]*mat2[0][1] + mat1[1][1]*mat2[1][1] }
};
}

Just call the fibonacci function from the main method with parameter passing .