It is typically called "performance optimization", but I would not call it "refactoring", since this term typically refers to changes in code which don't change its visible behaviour. And a change in Big-O is definitely something which I would call a visible change.
in doing so I will change the fundamental way the operation runs
In this case, your optimization is a rewrite of that function. Not every optimization, even if it changes "Big-O", is necessarily a rewrite, sometimes only small changes are necessary to achieve such an improvement, but even then, I am reluctant to use the term "refactoring" for this, because it might give a wrong impression.
EDIT: I checked Fowler's refactoring list, and among this ~100 named refactorings, the very last one is called "Substitute Algorithm". So if we take this as canonical reference, an optimization of the described form might be called a special kind of refactoring (but IMHO not a typical one). Note also, Fowler's goal with all refactorings was always to improve the design with focus on maintainability and evolvability of existing code without rewriting it, and clearly not performance optimization.