How does sudo decide whether to ask for a password, when given a command which doesn't actually need `sudo`?

sudo doesn’t know whether the command it’s asked to run needs to run as some other user (typically root), all it knows is its configuration. That determines which users are allowed to run sudo, with what users as “targets”, and for what commands; it also determines whether a password is needed, which one, and whether to keep an authentication token around.

If you’re using the default Debian configuration, the latter is most likely what’s involved here: sudo will ask you for your password the first time you use it in any given terminal, then it will keep an authentication token for a certain amount of time. If you re-use sudo in the same terminal within that timeframe, it won’t prompt you for a password.

In a typical configuration, the command is irrelevant. You need to enter your password the first time you use sudo, and you don't need your password in that particular shell for the next 15 minutes.

From the computer's perspective, there is no such thing as a “command that needs sudo”. Any user can attempt to run any command. The outcome may be nothing but an error message such as “Permission denied” or “No such file or directory”, but it's always possible to run the command.

For example, if you run du on a directory tree that has contents that you don't have permission to access, you'll get permission errors. That's what “permission denied” means. If you run sudo du, sudo runs du as root, so you don't get permission errors (that's the point of the root account: root¹ always has permission). When you run sudo du, du runs as root, and sudo is not involved at all after du has started. Whether du encounters permission errors is completely irrelevant to how sudo operates.

There are commands that need sudo to do something useful. Usefulness is a human concept. You need to use sudo (or some other methods to run the command as root) if the command does something useful when run as root but not when run under your account.

Whether sudo asks for your password depends on two things.

1. Based on the configuration, sudo decides whether you need to be authenticated. By default, sudo requires a password. This can be turned off in several ways, including setting the authenticate option to false and having an applicable rule with the NOPASSWD tag.
2. If sudo requires your password, it may be content to use a cached value. That's ok because the reason sudo needs your password is not to authenticate who's calling it (sudo knows what user invoked it), but to confirm that it's still you at the commands and not somebody who took control over your keyboard. By default, sudo is willing to believe that you're still at the commands if you entered your password less than 15 minutes ago (this can be changed with the timeout option). You need to have entered the password in the same terminal (so that if you remain logged in on one terminal then leave that terminal unattended and then use another terminal, someone can't take advantage of this to use sudo on the other terminal — but this is a very weak advantage and it can be turned off by setting the tty_tickets option to false).

¹ _{nearly, but that's beyond the scope of this thread.}

to a command which doesn't actually need sudo

It's not that a command needs or needs not sudo. When you run

sudo -u user command

the system executes command as the user.

Whether the invocation is successful or not, and whether a password is asked or not, depends on the security policy sudoers (usually configured in /etc/sudoers).