Can a Fibonacci function be written to execute in O(1) time?

by

Here is a near O(1) solution for a Fibonacci sequence term. Admittedly, O(log n) depending on the system Math.pow() implementation, but it is Fibonacci w/o a visible loop, if your interviewer is looking for that. The ceil() was due to rounding precision on larger values returning .9 repeating.

enter image description here

Example in JS:

function fib (n) {
  var A=(1+Math.sqrt(5))/2,
      B=(1-Math.sqrt(5))/2,
      fib = (Math.pow(A,n) - Math.pow(B,n)) / Math.sqrt(5);
      return Math.ceil(fib);
}

More Related Contents:

  1. What is a plain English explanation of “Big O” notation?
  2. How can I find the time complexity of an algorithm?
  3. What does O(log n) mean exactly?
  4. Difference between Big-O and Little-O Notation
  5. nth fibonacci number in sublinear time
  6. Is there an O(n) integer sorting algorithm?
  7. Hash table runtime complexity (insert, search and delete)
  8. John Carmack’s Unusual Fast Inverse Square Root (Quake III)
  9. Time complexity of Euclid’s Algorithm
  10. What would cause an algorithm to have O(log log n) complexity?
  11. Finding out nth fibonacci number for very large ‘n’
  12. What is pseudopolynomial time? How does it differ from polynomial time?
  13. Floating Point Divider Hardware Implementation Details
  14. how to calculate binary search complexity
  15. Time complexity of Sieve of Eratosthenes algorithm
  16. What would cause an algorithm to have O(log n) complexity?
  17. Are there any cases where you would prefer a higher big-O time complexity algorithm over the lower one?
  18. Argument for O(1) average-case complexity of heap insertion
  19. Sorting in linear time? [closed]
  20. Why is the complexity of computing the Fibonacci series 2^n and not n^2?
  21. How best to sum up lots of floating point numbers?
  22. Why is the time complexity of both DFS and BFS O( V + E )
  23. Test if a number is fibonacci
  24. Examples of Algorithms which has O(1), O(n log n) and O(log n) complexities
  25. An inverse Fibonacci algorithm?
  26. How can I convert between a double-double and a decimal string?
  27. Why is my recursive function so slow in R?
  28. How to convert decimal fractions to hexadecimal fractions?
  29. Do iterative and recursive versions of an algorithm have the same time complexity?
  30. Computational complexity of base conversion

Leave a Comment