hey so im having a bit of a hard time grasping empirical run-time analysis. so i have this question:
Suppose we have an O(1) function that took 8s to execute with n = 2,000. What would you expect the runtime to be if n = 10,000?
now here's my thought process which i believe is wrong: if T(n) is O(1) then T(n) = c * O(1) where c is just some constant. so solving for c we get c = T(n) / O(1). now since we know T(2000) = 8s and that n = 2000 we can just plug that in to solve for c, c = (8s) / (2000) which gives us 0.004. Now we have to the the same for n = 10,000 so in this case T(10,000)= c * O(1) in this case we can just plug in the same c we found earlier since it just a constant, and plug in 10,000 for O(1) which would gives us T(10,000) = (0.004) * 10,000 which equals 40s. im just not sure if my thought process was right on this one.
The correct answer is that we could not expect any particular time.
To say a function’s run-time O(1) is to say there is some number C such that the function always runs in less than C seconds. If the function ran in 8 s once, we know C is at least 8. But it could be a million. Or a septillion.
What O(1) does tell us is that the run time is limited regardless of what n is. That run time could go up and down with various n, but it is always limited by C.
In contrast, compare this to a function with run-time O(n). This means there is a number C such that the function’s run-time is always less than C*n seconds (except a finite number of exceptions are allowed). So we do not have a constant limit; we have a limit that depends on n. This function might take more and more time as n grows.
Or it might not. The O notation only tells you a limit on a function’s run-time. It does not tell you the actual run-time. If I know you had a gallon of gas in your car yesterday, and you went 30 miles, I know your car gets at least 30 miles per gallon. If you have two gallons in it today, I know you could go at least 60 miles, but maybe you could go more, and I do not know how far you will actually go. I know there is a limit on your travel, but I do not know what it actually is or how far you will go.