1. Start Contacts Undelete
2. Click on Navigation menu
3. Tap the 'Deleted Contacts'. Deleted contacts will be listed and a disclaimer will come up
4. The deleted list may be empty because of these several reasons:
a. By default, contacts are saved in your associated Google Account. If contacts are deleted from device or SIM storage they are immediately removed and, hence do not show up in the list
b. When you delete contacts from your Google Account, the contacts are still present in your devices's Google Account database. That is why it shows up in the deleted contacts list. The contacts are removed from your Google Account list once your phone book completes a sync with your Google A/c. If you sync too often, the contacts will be removed much faster than normal. In any case, if it has been several hours since you deleted a contact it has most likely been synced and, hence will not show up in deleted list
c. Some android device manufacturers configure the phone to delete the contacts immediately from Google account. In this case, the deleted contacts will not show up, ever
d. Note that you can still undelete your contacts after a month it has been deleted, by going through your Google account Restore feature. For more information click: Google Support - Contacts Restore