The answer depends on what exactly you mean by “regular expressions.” Classic regexes can be compiled into Deterministic Finite Automata that can match a string of length N in O(N) time. Certain extensions to the regex language change that for the worse. You may find the following document of interest: Regular Expression Matching Can Be … Read more
NOTE: While this answer was correct in 2012, engines use very different internal representations for both objects and arrays today. This answer may or may not be true. In contrast to most languages, which implement arrays with, well, arrays, in Javascript Arrays are objects, and values are stored in a hashtable, just like regular object … Read more
That depends on your set implementation. If you have a hash set (O(1) lookup), then the approach indicated by all the other posters is correct. Iterate across all the elements in the first set. If it’s in the second set, then add it to the result. This runs in O(n) time. If you have a … Read more
I love this problem. It’s a classic interview question and depending on how you think about it, you’ll end up getting better and better solutions. It’s certainly possible to do this in better than O(n2) time, and I’ve listed three different ways that you can think about the problem here. Hopefully this answers your question! … Read more
Quicksort’s performance is dependent on your pivot selection algorithm. The most naive pivot selection algorithm is to just choose the first element as your pivot. It’s easy to see that this results in worst case behavior if your data is already sorted (the first element will always be the min). There are two common algorithms … Read more
This follows easily from a simple fact in Calculus: and we have the following inequality: Here we can conclude that S = 1 + 1/2 + … + 1/n is both Ω(log(n)) and O(log(n)), thus it is Ɵ(log(n)), the bound is actually tight.
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
To understand the difference between polynomial time and pseudopolynomial time, we need to start off by formalizing what “polynomial time” means. The common intuition for polynomial time is “time O(nk) for some k.” For example, selection sort runs in time O(n2), which is polynomial time, while brute-force solving TSP takes time O(n · n!), which … Read more
Once expressed in big-O() notation, both are correct. However, during the derivation of the O() polynomial, in the case of binary search, only log2 is correct. I assume this distinction was the intuitive inspiration for your question to begin with. Also, as a matter of my opinion, writing O(log2 N) is better for your example, … Read more
O(log log n) terms can show up in a variety of different places, but there are typically two main routes that will arrive at this runtime. Shrinking by a Square Root As mentioned in the answer to the linked question, a common way for an algorithm to have time complexity O(log n) is for that … Read more