Why the c++’s implemented string::substr() doesn’t use the KMP algorithm (and doesn’t run in O(N + M)) and runs in O(N * M)? I assume you mean find(), rather than substr() which doesn’t need to search and should run in linear time (and only because it has to copy the result into a new string). … Read more
// returns -1 if there is no element that is the majority element, otherwise that element // funda :: if there is a majority element in an array, say x, then it is okay to discard // a part of that array that has no majority element, the remaining array will still have // x … Read more
I have to agree that it’s pretty weird the first time you see an O(log n) algorithm… where on earth does that logarithm come from? However, it turns out that there’s several different ways that you can get a log term to show up in big-O notation. Here are a few: Repeatedly dividing by a … Read more
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
An ArrayList in Java is a List that is backed by an array. The get(index) method is a constant time, O(1), operation. The code straight out of the Java library for ArrayList.get(index): public E get(int index) { RangeCheck(index); return (E) elementData[index]; } Basically, it just returns a value straight out of the backing array. (RangeCheck(index)) … Read more
Your n/2 + n/3 + n/5 + … n/97 is not O(n), because the number of terms is not constant. [Edit after your edit: O(n2) is too loose an upper bound.] A loose upper-bound is n(1+1/2+1/3+1/4+1/5+1/6+…1/n) (sum of reciprocals of all numbers up to n), which is O(n log n): see Harmonic number. A more … Read more
Here a more mathematical way of seeing it, though not really complicated. IMO much clearer as informal ones: The question is, how many times can you divide N by 2 until you have 1? This is essentially saying, do a binary search (half the elements) until you found it. In a formula this would be … Read more
tl;dr: No and no. Let’s start with sort/2 which ideally would need n ld(n) comparisons. Fine, but how long does one comparison take? Let’s try this out: tails(Es0, [Es0|Ess]) :- Es0 = [_|Es], tails(Es, Ess). tails([],[[]]). call_time(G,T) :- statistics(runtime,[T0|_]), G, statistics(runtime,[T1|_]), T is T1 – T0. | ?- between(12,15,I), N is 2^I, length(L,N),maplist(=(a),L), tails(L,LT), call_time(sort(LT,LTs), … Read more
New answer As of update 6 within Java 7’s lifetime, the behaviour of substring changed to create a copy – so every String refers to a char[] which is not shared with any other object, as far as I’m aware. So at that point, substring() became an O(n) operation where n is the numbers in … Read more
One of the things you have to realise when dealing with O notation is that it is often very important to understand what n is. If the n is something related to something you can control (eg: the number of elements in a list you want sorted) then it makes sense to look hard at … Read more