I agree with ysavir: I do not mind being exposed to ads related to my current search - I understand it is the price to pay for a free service... I mind my searches being stored and attached to my (not event anonymous) profile in a database.

And the "not even anonymous" is not an option: to be able to have a fully functioning phone, I hardly can escape declaring my full details to Google.

And this is clearly an "evil" choice of Google: I never created a Linux, Debian, Ubuntu or Mint account to keep my desktop computer up-to-date and featured by additional apps.

Ehhhhhh I'm paying for it by viewing the sponsored (and non-sponsored) ads.

Any tracking that isn't announced to the user is not a cost, but is espionage.