f ∈ O(g) says, essentially For at least one choice of a constant k > 0, you can find a constant a such that the inequality 0 <= f(x) <= k g(x) holds for all x > a. Note that O(g) is the set of all functions for which this condition holds. f ∈ o(g) … Read more
Remember that log(n!) = log(1) + log(2) + … + log(n-1) + log(n) You can get the upper bound by log(1) + log(2) + … + log(n) <= log(n) + log(n) + … + log(n) = n*log(n) And you can get the lower bound by doing a similar thing after throwing away the first half … Read more
There’s a distinction between “are these constants meaningful or relevant?” and “does big-O notation care about them?” The answer to that second question is “no,” while the answer to that first question is “absolutely!” Big-O notation doesn’t care about constants because big-O notation only describes the long-term growth rate of functions, rather than their absolute … 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 … Read more
You can implement a stack with O(1) pop(), push() and get_min(): just store the current minimum together with each element. So, for example, the stack [4,2,5,1] (1 on top) becomes [(4,4), (2,2), (5,2), (1,1)]. Then you can use two stacks to implement the queue. Push to one stack, pop from another one; if the second … Read more
You have two variables here, m and n, where m is the length of the input and n is the number of items in the hash. The O(1) lookup performance claim makes at least two assumptions: Your objects can be equality compared in O(1) time. There will be few hash collisions. If your objects are … Read more
Since it doesn’t seem like anyone has done this before I thought it’d be good idea to have it for reference somewhere. I’ve gone though and either via benchmark or code-skimming to characterize the array_* functions. I’ve tried to put the more interesting Big-O near the top. This list is not complete. Note: All the … Read more
A particular feature of a HashMap is that unlike, say, balanced trees, its behavior is probabilistic. In these cases its usually most helpful to talk about complexity in terms of the probability of a worst-case event occurring would be. For a hash map, that of course is the case of a collision with respect to … Read more
The time complexity, in Big O notation, for each function: int recursiveFun1(int n) { if (n <= 0) return 1; else return 1 + recursiveFun1(n-1); } This function is being called recursively n times before reaching the base case so its O(n), often called linear. int recursiveFun2(int n) { if (n <= 0) return 1; … Read more
public static int[] merge(int[] a, int[] b) { int[] answer = new int[a.length + b.length]; int i = 0, j = 0, k = 0; while (i < a.length && j < b.length) answer[k++] = a[i] < b[j] ? a[i++] : b[j++]; while (i < a.length) answer[k++] = a[i++]; while (j < b.length) answer[k++] = … Read more