What does big O stand for?

Big O notation is about putting an upper bound on the ORDER of the runtime.

How can you physically calculate how long a program will take?

You can always time your program in seconds of real time: start a stopwatch when you begin running the program, and stop it when the program finishes. At the command prompt, you can do this by running time python <program>.py, which will tell you how many seconds your program took.

Why did sys time show as 0 seconds, isn't that impossible?

The time command only measures down to the nearest one-thousandth of a second, so if the program runs faster than one-thousandth of a second, it may be reported as running in 0 seconds.

What other types of searches exist, if any?

LOTS of other search algorithms exist, and some of them take advantage of different ways of storing and looking up data. To learn more about this, I recommend CS 35!