How to find if an application is installed or not in your Linux distro, depends on that distro’s package manager.

Find out if an application is installed in Debian with dpkg -l:
This also works on Ubuntu/Linux Mint or other dpkg based distros.
$ dpkg -l | grep vim
ii vim 2:7.3.154+hg~74503f6ee649-2ubuntu3.1 Vi IMproved - enhanced vi editor
ii vim-common 2:7.3.154+hg~74503f6ee649-2ubuntu3.1 Vi IMproved - Common files
ii vim-runtime 2:7.3.154+hg~74503f6ee649-2ubuntu3.1 Vi IMproved - Runtime files
ii vim-tiny 2.7.3.154+hg~74503f6ee649-2ubuntu3.1 Vi IMproved - enhanced vi editor - compact version
If you don’t get any output, the package is not installed.
You can list all the installed packages with dpkg -l | less
Find out if a package is installed in Fedora with rpm -qa:
This also works on OpenSuse, Mandrake, CentOS or other rpm based distros.
$ rpm -qa | grep vim
vim-7.3-22.1.3.x86_64
vim-base-7.3-22.1.3.x86_64
If you don’t get any output, the package is not installed.
You can list all the installed packages with rpm -qa | less