Yes, in your case*1 string concatenation requires all characters to be copied, this is a O(N+M) operation (where N and M are the sizes of the input strings). M appends of the same word will trend to O(M^2) time therefor. You can avoid this quadratic behaviour by using str.join(): word = ”.join(list_of_words) which only takes … Read more
It is important to remember that the notation, whether O, Ω or Θ, expresses the asymptotic growth of a function; it does not have anything intrinsically to do with algorithms per se. The function in question may be the “complexity” (running time) of an algorithm, either worst-case, best-case or average-case, but the notation is independent … Read more
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
The comment is simply wrong. Yes, it is a red-black tree, O(log(n)) for inserts. Taking a look with Reflector bears this out, the private AddIfNotPresent() method contains a while() loop to find the insertion point, using normal red-black node traversal. This doc bug has already been submitted by you-know-who.
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
This question can be easily solved with the help of set in O(N) time and space complexity.First add all the elements of array into set and then traverse each element of array and check whether K-ar[i] is present in set or not. Here is the code in java with O(N) complexity : boolean flag=false; HashSet<Long> … Read more
Your analysis is wrong, both insertion and deletion is O(n) for a sorted array, because you have to physically move the data to make space for the insertion or compress it to cover up the deleted item. Oh and the worst case for completely unbalanced binary search trees is O(n), not O(logn).
C++ strings are mutable, and pretty much as dynamically sizable as a StringBuffer. Unlike its equivalent in Java, this code wouldn’t create a new string each time; it just appends to the current one. std::string joinWords(std::vector<std::string> const &words) { std::string result; for (auto &word : words) { result += word; } return result; } This … Read more
Use LRANGE with LTRIM in a pipeline. The pipeline will be run as one atomic transaction. Your worry above about WATCH, EXEC will not be applicable here because you are running the LRANGE and LTRIM as one transaction without the ability for any other transactions from any other clients to come between them. Try it … Read more
Consider: f1(n) = n2 f2(n) = n + 1000 Clearly f1 is O(n2) and f2 is O(n). For a small input (say, n=5), we have f1(n) = 25 but f2(n) > 1000. Just because one function (or time complexity) is O(n) and another is O(n2) doesn’t mean that the former is smaller for all values … Read more