Если никто до этого момента не обращался к домену example.com, то может и мгновенно.
Если обращался, то это обращение висит в кеше. В ns записи обычно указывается TTL, но некоторые DNS сервера могут его игнорить и работать по умолчанию - хранить информацию в кеше до суток.
То есть через сутки - данные о домене должны устареть на всех кешах, и обновиться с ваших NS серверов свежими.