Big O Notation – Understanding Comparison in Algorithms

algorithmslinked list

I was going through this heavily discussed and highly voted question on SO and stumbled across one comment that got 5 upvotes.

So I assume this was a great comment.But it got my head spinning at the same time. Can any one explain this comment? The comment says:

You can't compare big-O values directly without thinking about constant factors. For small lists (and most lists are small), ArrayList's O(N) is faster than LinkedList's O(1).

Best Answer

all O(1) means is that it takes constant time, but not necessarily 1 unit of time. So for a concrete example, let's say the LinkedList takes 3 seconds to access any element. This is in constant time, but it is fairly slow. It is not hard to imagine a situation where we have an Arraylist with O(n) access, but where n is small enough that no element would take more than 2 seconds to access. In such cases, the ArrayList would actually be faster than the LinkedList.

Related Solutions

C++ – Using std::sort et al. with user-defined comparison routine

Your question seems to boil down to whether or not C++'s std::sort can be used with comparison functions that do not behave like the < operator. Operator < is a strict weak order, not a total order. Any container or algorithm in the C++ standard library that depends on operator < assume that it forms a strict weak ordering, and if you violate that assumption then havoc can ensue (as you've seen.) So, to bluntly answer the question in your title, std::sort works absolutely fine with custom comparator routines, but those custom routines must behave properly.

As for how to generate a proper ordering for std::sort given a possible total ordering, you might try the following. Given a custom ordering function f, define a new ordering function f_weak like so:

template <typename T, typename F>
auto f_weak(F comparator)
{
    return [comparator](T a, T b) {
               return comparator(a, b) // true if a <= b
                        && a != b;
    };
}

and then pass f_weak<T>(f) as the last parameter to std::sort. This code is untested, and uses some modern C++ features, but I'm sure you get the gist of it.

Big O Notation of Randomness – Algorithm Analysis

The worst-case is O(∞). The best-case is Ω(n²), because you have to generate n numbers, and for each number generated you have to search a list of length n whether or not the number is already in there.

Best Answer

Related Solutions

C++ – Using std::sort et al. with user-defined comparison routine

Big O Notation of Randomness – Algorithm Analysis

Related Topic