Dunno what you mean by 'tsearch' ?? Never heard of it myself.
Yes, using a wildcard search with LIKE will involve a table scan and that could be slow - if you had a million records or so that is. Searching through a few tens of thousands of records should not be a problem. If it is then that will be because your shared server is overcrowded or just plain slow. Change host to solve that problem.
If you did have a large database then using full text search would improve performance.