My dad has a PC and a mobile that he'd never connected to the wifi because reasons. He put a nonsense word in google with no hits like 'spongeriftallytastic' and then put it in his phone, and it came up as the first suggested word.
How does it do this? He has GPS and such off and as much privacy settings on as possible whilst maintaining use of 4g. He uses chrome on both machines, I believe he has a whatever account on his phone (Android) so he can access the store but otherwise he doesn't use it for that. He doesn't use it as a phone by the way, he essentially uses it as a laptop which is supposed to be unconnected from our local wifi network insofar as websites know.