Are you saying I should speak to my host and ask them to execute the script from there???
No, my suggestion was for you to execute sitemap generator from command line. It is required to have SSH access the host (you can ask your hosting support whether you have it).
I am on a shared server, will this make any difference???
If you are on a shared server, you are not allowed to change php settings on your own, so you should contact your hosting support regarding increaseing max_execution_time setting in php.ini
Another option is to use "Save state" option of Sitemap Generator:
1. Execute generator and check how long it is running before it's interrupted (for instance, 90 seconds)
2. Set "Save state" option to 60 seconds
3. Execute generator again
4. After it is stopped, open "Crawling" page again and re-execute generator with "Resume generation" checkbox enabled. It will then load crawling state from the file and continue execution.
You might need to repeat step 4 multiple times until full sitemap is created.