Update Fibonacci.java

TheAlgorithms · debasishbsws · Oct 30, 2022 · Oct 28, 2022 · Oct 29, 2022 · Oct 29, 2022
commit 1810d4af2e6519c9059aff0f1f6760738e5ad332
@@ -80,6 +80,30 @@ public static int fibBotUp(int n) {
      * @author Shoaib Rayeen (https://github.com/shoaibrayeen)
      */
     public static int fibOptimized(int n) {
-        return (int) (Math.pow(((1 + Math.sqrt(5)) / 2), n) / Math.sqrt(5));
-    }
+        if (n == 0) {
+            return 0;
+        }
+        int prev = 0, res = 1, next;
+        for (int i = 2; i <= n; i++) {
+            next = prev + res;
+            prev = res;
+            res = next;
+        }
+        return res;
+}
+
+    /**
+    * We have only defined the nth Fibonacci number in terms of the two before it. Now, we will look at Binet's formula to calculate the nth Fibonacci number in constant time.
+    * The Fibonacci terms maintain a ratio called golden ratio denoted by Φ, the Greek character pronounced ‘phi'.
+    * First, let's look at how the golden ratio is calculated: Φ = ( 1 + √5 )/2 = 1.6180339887...
+    * Now, let's look at Binet's formula: Sn = Φⁿ–(– Φ⁻ⁿ)/√5
+    * We first calculate the squareRootof5 and phi and store them in variables. Later, we apply Binet's formula to get the required term.
+    * Time Complexity will be O(1)
+    */
+
+    public static int fibBinet(int n) {
+        double squareRootOf5 = Math.sqrt(5);
+        double phi = (1 + squareRootOf5)/2;
+        int nthTerm = (int) ((Math.pow(phi, n) - Math.pow(-phi, -n))/squareRootOf5);
+        return nthTerm;
 }