I've read various wiki articles and guides on how to get through the activity, and playing a few routes, I noticed that the number of levels that a companion levels up each time seems to gradually decrease as his level increases. However, none of the guides I've looked at give me any idea of how many times I'll have to play this game to level up my companions. Does anyone know an approximate, ballpark number for how many trips it would take to get each tier of companion (easy, medium, hard) up to level 99?
If you have the correct equipment in your inventory for easy Trekking - it should take you no longer than a few days - providing this is the only thing you do on RS when you're logged in.
However, now with the introduction of EOC - this will take a bit longer. I would estimate around 2 weeks maximum.