LeetCode 509. Fibonacci Number

LeetCode Notes [17]

John Lu
Nov 21, 2022

Problem

Intuition

Optimal Substructure: F(n) = F(n-1) + F(n-2), for n > 1

Solution 1: Dynamic Programming

Complexity Analysis

  • Time complexity : O(n).
    The recursive function is run once for each of the n nodes, and the body of the recursive function is O(1). Therefore, this gives a total of O(n).
  • Space complexity : O(n).

Solution 2: Three variables

Complexity Analysis

  • Time complexity : O(n).
  • Space complexity : O(1).

--

--

John Lu
John Lu

Written by John Lu

AI Engineer. Deeply motivated by challenges and tends to be excited by breaking conventional ways of thinking and doing. He builds fun and creative apps.

No responses yet