As far as I can tell, for purely functional sequence types the naive implementation of a sequence would result in O(n) time complexity for element access and a better implementation (as described by Chris Okasaki) enjoys O(log n) complexity, for a sequence of length n.
What is the time complexity of accessing an arbitrary element in a boost::hana::tuple with operator[]? If it's neither of the above, how is it implemented?
The runtime complexity is O(1). Basically, it's as fast as accessing a struct member (because that's essentially what it is). The implementation is similar to a std::tuple.
As for the compile-time complexity, it's also O(1), but you do pay O(n) compile-time complexity for creating the tuple at the beginning. Also, here, I measure compile-time complexity in terms of the number of template instantiations, but that's a very naive way of measuring the final compilation time.
Edit: Here's the gist of how tuple access works:
// Holds an element of the tuple
template <std::size_t n, typename Xn>
struct elt { Xn data_; };
// Inherits multiply from the holder structs
template <typename Indices, typename ...Xn>
struct tuple_impl;
template <std::size_t ...n, typename ...Xn>
struct tuple_impl<std::index_sequence<n...>, Xn...>
: elt<n, Xn>...
{ /* ... */ };
template <typename ...Xn>
struct basic_tuple
: tuple_impl<std::make_index_sequence<sizeof...(Xn)>, Xn...>
{ /* ... */ };
// When you call get<n>(tuple), your tuple is basically casted to a reference
// to one of its bases that holds a single element at the right index, and then
// that element is accessed.
template <std::size_t n, typename Xn>
Xn const& get(elt<n, Xn> const& xn)
{ return xn.data_; }