I find that to be pretty typical - naive solutions are bad for Big-O reasons.
If you solve the math on paper and implement a straightforward algorithm, you get the fastest possible solution.
If you push some of that math into the type system of your language, you get something that should be Big-O equivalent to the fastest possible solution, but the machinery of the type system never gets fully optimized away. There might be other advantages, though, of having that machinery - your compiler might be able to detect errors in your code, or you might be able to use higher-level constructs to make more concise code. Maybe.
