Without knowing your domain name, this is hard to answer. This is mainly because the parent domain controls this, overall. org, net, and com happen fairly fast, as do info and several other TLDs. Some, however, only publish once or twice a day, so it could vary widely.
For future changes, I highly recommend doing NS record changes with these procedures:
If you can, serve the data from the old and new hosting companies. This ensures things won't break during the transition. You should keep the old site up for at least the TTL period of the longest TTL in your zone. Both new and old should serve as close to the same data as you can, and the NS records should point ONLY to the new servers.
If you cannot keep the DNS servers up on both locations it is harder and you will have an outage. To control how long that is:
- Set the TTL on your NS records to something small, like 300.
- Wait until the previous TTL has expired. If you used 3600, an hour. If it's longer, you should expect to wait that long.
At this point, you've done the best you can. Point the NS records from your parent zone to your new ones (through your registrar interface probably.) If you have both new+old running, you should get no outage. If you had to do it the hard way, you will get an outage of about the TTL period for new lookups until the NS records expire AND your parent updates their servers.