Algorithms

Strategy Talk about time and space complexity through out the program look at the input parameters to the function Terminology $O(nlogn + n^2)$ asymptotically is $O(n^2)$. If you write $O(n^2)$ explain its the asymptotic time complexity. Applications Common time complexity patterns: $O(2^N)$, $O(3^N)$: Permutation (e.g., NP hard problems) $O(N^2)$, $O(N^3)$: Recursion / generate subsets, nested loops $O(NlogN)$: Sorting / heap $O(N)$: Iteration, pointers/sliding window, common array operations $O(logN)$: Binary search / exponentially sized steps search $O(1)$: Hashmap or index of array Time Complexity Names $O(2^N)$, exponential time $O(N^2)$, quadratic time $O(NlogN)$, linearithmic time $O(N)$, linear time $O(logN)$, logarithmic time $O(1)$, constant time Space Complexity Space = Input + Auxilary + Output ...

The Fibonacci sequence is a sequence in which each number is the sum of the two previous ones, starting with 0 and 1 as the base cases. A Fibonacci number is a number in the Fibonacci sequence. The golden ratio can be computed from the ratio between two Fibonacci numbers in consecutive sequence, as the sequence approaches infinity. Here we will talk about how to compute the nth number in the Fibonacci sequence. ...