T(n): running time of Algo A. We just care about the upper bound and lower bound of T(n) The statement: T(n) >= O(n^2) Upper bound: Because T(n) >= O(n^2), then there’s no information about upper bound of T(n) Lower bound: Assume f(n) = O(n^2), then the statement: T(n) >= f(n), but f(n) could be anything that is “smaller” than n^2 , Ex: constant, n,…, So there’s no conclusion … Read more
In the absolute worst case, a binary tree with N elements would be like a linked list.Hence, there would be N levels, and a search would take N traversals. That’s why it’s O(N) in the worst case.And this is why we need to balance the trees to achieve O(log N) search.
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
What you have coded in your example is very similar to a depth first search. So, that’s one answer. A depth first search algorithm without any special characteristics ( like re-convergent paths that can be optimized out ), should be n^n. This is actually not a contrived example. Chess programs operate on the same algorithm. … Read more
It means that the thing in question (usually running time) scales in a manner that is consistent with the logarithm of its input size. Big-O notation doesn’t mean an exact equation, but rather a bound. For instance, the output of the following functions is all O(n): Because as you increase x, their outputs all increase linearly – if there’s … Read more
Do you know, f(n) = O(g(n)) implies f(n) <= constant* g(n), right? In other words, it means, when you plot the graph of f(n) and g(n) then after some value of, g(n) will always be more than f(n). Here g(n) is N^3 and remaining comes in f(n). Now, N^3 is always >= options a, b, c. hence answer id D 🙂 Edit: Following statements are true, n=O(n) n=O(n^2) n=O(n^3) But only n = O(n) is tight upper bound and that is what … 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
While trying to understand the difference between Theta and O notation I came across the following statement : But I do not understand this. The book explains it mathematically, but it’s too complex and gets really boring to read when I am really not understanding. Can anyone explain the difference between the two using simple, … Read more
As @emory pointed out, it is provably impossible to determine the big-O time complexity of an arbitrary piece of code automatically (the proof is a reduction from the halting problem). However, there are tools that can attempt to measure the complexity of a piece of code empirically by running it on several different inputs. One … 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