What good does splicing Big-Oh into the process do, when computer science enrollment is in steady decline, and understanding Big-Oh is pointless without first understanding the costs of polynomial algorithms? It would be nice if our calculus students knew Lebesgue integration too, but I would offer that the calculus sequence is not the right time. If the kids are in college, they can take Intro. to Comp. Sci., and if the kids are in high school, they probably shouldn't worry about Big-Oh at all.
The biggest revision high school math needs is 1. A course which instills students with a basic statistical fluency, so they can read the newspaper and endure advertisements with a critical mind, and 2. A course for advanced students which teaches discrete math and basic non-geometrical proofs, for our increasingly discrete world.