Перевод Worst case space complexity
Worst case performance — вычислительная сложность в худшем случае (имеется в виду случай организации входных данных)
Best case performance — вычислительная сложность в лучшем случае
Average case performance — вычислительная сложность в среднем (?)
Worst case space complexity — пространственная сложность в худшем случае (характеризуется ростом требуемого объёма памяти при росте размерности задачи). Слово «auxiliary», кажется, вырвано из контекста.
И n2 — это, конечно, n2 (n квадрат).
Ну вот мне как человеку, имеющему диплом переводчика, дословные кальки с языка оригинала всегда режут слух. Конечно, если термин именно в таком виде стал общеупотребительным в специальной литературе, то тут ничего не поделаешь. Но там где такой ситуации нет, мне кажется нужно использовать более доступный (близкий к языку перевода) вариант объяснения термина.