Why call it a "major" revision if the suggested changes are seemingly minor?

It varies by journal I'm sure but sometimes the line between "minor" and "major" revision is set by whether the reviewers wish to see the changes authors make in response to their comments before recommending acceptance.

A "minor" revision would go straight back to the editor and then to production while a "major" one goes back to the reviewers first. This might not be related to the amount of work required.

In your case it's possible that the reviewer wants to be sure you include an appropriate section about the limitations of the algorithm otherwise they wouldn't recommend acceptance.

Just make the required changes and send the paper back to the editor. Don't worry about what it's called – it makes no difference to your situation whether it's called a major revision, a minor revision or a super-special changey thing.

As to why it was described as a major revision, only the editor really knows that. Maybe it was even just a mistake.

(Background disclaimer: I’ve seen this from the perspective of an author and reviewer, not an editor.)

Major/minor can refer to the importance of an edit, not just to its size.

For instance, if a key statement in the paper is inaccurate (e.g. if a theorem is incorrect as stated), then even if the changes needed to fix it are small, the reviewer may describe this as “major revisions”, and the editor may agree. So the referee is saying “you seriously need to fix this!” not just “consider adding something about this?” For some journals/conferences, it also has the practical effect that the referees get to see the revised version before it’s accepted, and check that the required changes have been made — so, again, a referee may call a revision “major” because they feel it’s essential for correctness, and want to ensure it has been made before endorsing the paper for publication.