Command Not Found

My machine's BASH has just received a brand new upgrade! From now on, whenever I type a command to open some application which is not installed in my Ubuntu system, the repositories are automatically scanned and, if there is an application with the given name, it will be suggested for installation.

Confused? Here's an example, I'll try to open gedit, which is not installed:

tiagoboldt@Niath:~$ gedit
The program 'gedit' is currently not installed. You can install it by typing:
sudo apt-get install gedit
bash: gedit: command not found
tiagoboldt@Niath:~$

This feature should be installed by default, but you can also install it through the command-not-found package, available in the repositories.

Edit:
There has been some discussion about how fast the output comes out, if it slow or not, so, see it for yourself:

tiagoboldt@Niath:~$ time kedit
The program 'kedit' is currently not installed. You can install it by typing:
sudo apt-get install kedit
Make sure you have the 'universe' component enabled
bash: kedit: command not found

real 0m0.154s
user 0m0.108s
sys 0m0.028s

Less than 0.2 seconds, yes, it is fast!