O(n!) isn’t equivalent to O(n^n). It is asymptotically less than O(n^n). O(log(n!)) is equal to O(n log(n)). Here is one way to prove that: Note that by using the log rule log(mn) = log(m) + log(n) we can see that: Proof that O(log(n!)) ⊆ O(n log(n)): Which is less than: So O(log(n!)) is a subset of O(n log(n)) Proof that O(n log(n)) ⊆ O(log(n!)): Which is greater … Read more
Yes, nested loops are one way to quickly get a big O notation. Typically (but not always) one loop nested in another will cause O(n²). Think about it, the inner loop is executed i times, for each value of i. The outer loop is executed n times. thus you see a pattern of execution like this: … Read more
The definition of big O is: O(f(n)) = { g | there exist N and c > 0 such that g(n) < c * f(n) for all n > N } In English, O(f(n)) is the set of all functions that have an eventual growth rate less than or equal to that of f. So … Read more
You model the time function to calculate Fib(n) as sum of time to calculate Fib(n-1) plus the time to calculate Fib(n-2) plus the time to add them together (O(1)). This is assuming that repeated evaluations of the same Fib(n) take the same time – i.e. no memoization is used. T(n<=1) = O(1) T(n) = T(n-1) … Read more