The big O notation can be used to determine the growth rate of any function. In this case, it seems the book is not talking about the time complexity of computing the value, but about the value itself. And n(n+1)/2 is O(n^2).
Finding articulation vertices is an application of DFS. In a nutshell, Apply DFS on a graph. Get the DFS tree. A node which is visited earlier is a “parent” of those nodes which are reached by it and visited later. If any child of a node does not have a path to any of the … Read more
For String, StringBuffer, and StringBuilder, charAt() is a constant-time operation. For StringBuffer and StringBuilder, deleteCharAt() is a linear-time operation. StringBuffer and StringBuilder have very similar performance characteristics. The primary difference is that the former is synchronized (so is thread-safe) while the latter is not.
This seems to be a question of mislead, because I happened to read that book just now. This part of text in the book is a typo! Here is the context: =================================================================== Question: What is the running time of this code? 1 public String makeSentence(String[] words) { 2 StringBuffer sentence = new StringBuffer(); 3 for … Read more
I’d try to keep it away from computers altogether. Ask your audience how they find an entry in a dictionary. (A normal dictionary of word definitions.) The naive implementation is to start at the very beginning, and look at the first word. Oh, that’s not the word we’re looking for – look at the next … Read more
If you take multiplication as O(1), then yes, O(N) is correct. However, note that multiplying two numbers of arbitrary length x is not O(1) on finite hardware — as x tends to infinity, the time needed for multiplication grows (e.g. if you use Karatsuba multiplication, it’s O(x ** 1.585)). You can theoretically do better for … Read more
One important thing most people forget when talking about Big-O, thus I feel the need to mention that: You cannot use Big-O to compare the speed of two algorithms. Big-O only says how much slower an algorithm will get (approximately) if you double the number of items processed, or how much faster it will get … Read more
The worst case of merge sort will be the one where merge sort will have to do maximum number of comparisons. So I will try building the worst case in bottom up manner: Suppose the array in final step after sorting is {0,1,2,3,4,5,6,7} For worst case the array before this step must be {0,2,4,6,1,3,5,7} because … Read more
A jump table is used, making the pattern-match a constant time operation. Unfortunately I’m unable to find an up-to-date citation for this, although this page mentions the implementation of Cmm-level switch statements as jump tables, and this old tagging design document uses a case on a Bool as an example, producing a jump table.