Why call it a "major" revision if the suggested changes are seemingly minor? I recently got a major revision from an applied math journal. However the only change the reviewer has asked is to put a remark on some theorem in the paper (why the specified theorem will not work under some general case). According to the reviewers the rest of the paper is fine. 

I am slightly confused why is it a "major revision". Any suggestion will be helpful.
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.