Write a program (in Python) that prompts the user for a sentence (a string), saves that string as a list of characters, reverses the list, and displays the reversed sentence. For example, if the user enters Hello dad! , the program should display !dad olleH .

DO NOT USE the list method named "reverse" that is available in Python - you must write a loop to swap the list elements.

Make this program as efficient as possible. Write a comment in the beginning of the program stating the program's computational complexity using big-O notation.