Big-O is only strictly meaningful in terms of asymptotic behavior; as soon as you start talking about specific values of N, you have to care about constant factors.

In this case, the constant factors will probably be quite different because the goal is to make better use of CPU cache.

I mean, it depends on your data access patterns. Arrays are good for some things, trees are good for other things. Here's another option.