Why does it take so long for Ubuntu to say "command not found"

Solution 1:

The shell does more than just looking in $PATH. If a command is not found, the bash function command_not_found_handle is executed which in its turn call the python script /usr/lib/command-not-found. This searches in the packages list for programs that should be installed for the command to work. In the case of a typo which you know how to solve, just press Ctrl + C to abort the search process.

Example of a useful message for a typo:

$ aptget update
No command 'aptget' found, did you mean:
 Command 'apt-get' from package 'apt' (main)
aptget: command not found

Example of a useful message for a missing package:

$ deja-dup
The program 'deja-dup' is currently not installed.  You can install it by typing:
sudo apt-get install deja-dup

See also the rationale behind this, https://wiki.ubuntu.com/CommandNotFoundMagic

Solution 2:

It's because of a package named "command-not-found". You can uninstall it to shorten the response time.