Finally! Following up leads in sdcvvc’s answer, we have it: the O(n log n) algorithm for the problem! It is simple too, after you understand it. Those who guessed FFT were right. The problem: we are given a binary string S of length n, and we want to find three evenly spaced 1s in it. … Read more
I found the nice resource Standard C++ Containers. Probably this is what you all looking for. VECTOR Constructors vector<T> v; Make an empty vector. O(1) vector<T> v(n); Make a vector with N elements. O(n) vector<T> v(n, value); Make a vector with N elements, initialized to value. O(n) vector<T> v(begin, end); Make a vector and copy … Read more
You will have to go to the formal definition of the big O (O) in order to answer this question. The definition is that f(x) belongs to O(g(x)) if and only if the limit limsupx → ∞ (f(x)/g(x)) exists i.e. is not infinity. In short this means that there exists a constant M, such that … 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 book Java Generics and Collections has this information (pages: 188, 211, 222, 240). List implementations: get add contains next remove(0) iterator.remove ArrayList O(1) O(1) O(n) O(1) O(n) O(n) LinkedList O(n) O(1) O(n) O(1) O(1) O(1) CopyOnWrite-ArrayList O(1) O(n) O(n) O(1) O(n) O(n) Set implementations: add contains next notes HashSet O(1) O(1) O(h/n) h is … Read more
From David Morgan-Mar’s Esoteric Algorithms page: Intelligent Design Sort Introduction Intelligent design sort is a sorting algorithm based on the theory of intelligent design. Algorithm Description The probability of the original input list being in the exact order it’s in is 1/(n!). There is such a small likelihood of this that it’s clearly absurd to … Read more
First let’s understand what big O, big Theta and big Omega are. They are all sets of functions. Big O is giving upper asymptotic bound, while big Omega is giving a lower bound. Big Theta gives both. Everything that is Ө(f(n)) is also O(f(n)), but not the other way around. T(n) is said to be … Read more
This is called finding the k-th order statistic. There’s a very simple randomized algorithm (called quickselect) taking O(n) average time, O(n^2) worst case time, and a pretty complicated non-randomized algorithm (called introselect) taking O(n) worst case time. There’s some info on Wikipedia, but it’s not very good. Everything you need is in these powerpoint slides. … Read more
There can be many reasons to prefer an algorithm with higher big O time complexity over the lower one: most of the time, lower big-O complexity is harder to achieve and requires skilled implementation, a lot of knowledge and a lot of testing. big-O hides the details about a constant: algorithm that performs in 10^5 … Read more
If it’s a list of string, just use the c() function : R> LL <- list(a=”tom”, b=”dick”) R> c(LL, c=”harry”) $a [1] “tom” $b [1] “dick” $c [1] “harry” R> class(LL) [1] “list” R> That works on vectors too, so do I get the bonus points? Edit (2015-Feb-01): This post is coming up on its … Read more