"Order of magnitude" for qualitative changes

Solution 1:

I think level is a suitable word.

Specifically in the context of the polynomial hierarchy, one might informally think of a problem known to be NP-complete as one level harder than a problem in P (provided of course the hierarchy does not collapse at this level).

More generally, level generally connotes stratification in terms of achievement/difficulty. It's a gamey word, for example: your average computer game addict is usually fairly obsessed with the level achieved so far.

Solution 2:

Complexity. For this Big-O Know thy complexities! cheat sheet, it explicitly divides algorithms into time complexity and space complexity.

The big-O originally stands for "order of" ("Ordnung", Bachmann 1894), and is thus a roman letter. (source)

An NP hard problem is one order of complexity greater than an NP problem.

Going back to the cheat sheet, a Bubble sort is one order of time complexity worse than a Quicksort.