Big O and Time Complexity

Question 1

Since Big O is just an approximation you can not compute the real time but yes you can have some estimation. In your case it would be

1 M ~ 5 min
4 M ~ 5 *(4*4) min ~ 80 min.

Note : I used symbol ~ to show approximation.

O(N^2) => problem with size N will take approximately N^2 time

M will take approximately M^2 time

O(M)~ O(1M) 
=> 1^2*M^2 
=> M^2 
=> 5 min


O(4M) ~ (4M)^2 
=> 4^2*M^2 
=> 16*M^2 
=> 16*5 
=> 80 min

Question 2

If the complexity is O(N^2), this means the time for a problem of size N is roughly k*N^2 for some fixed but unknown value of k.

If you represent the approximate time to run the algorithm on a problem of size N as T(N), then mathematically you have this:

T(N)   = k*N^2
T(M)   = k*M^2
T(M)   = 5 minutes
T(4*M) = k*(4*M)^2 
       = 16*k*M^2 
       = 16*T(M)
       = 80 minutes

Question 3

In a nutshell, not necesarily.

When we say that a problem's time complexity is O(N²), what that means is that given a problem of size N, the time it takes to run conforms roughly to some equation of the form a + bN + cN², where a, b, and c are unknown coefficients.

This does mean that eventually the N² term will dominate the run-time. But eventually might be a long time away. There might be a large constant set-up time built in (that is, a in the formula above is big), such that 4 of the 5 minutes of your hypothetical scenario don't vary with problem size. In that case, perhaps a problem of size 4M might take less than twice as long to run.

Situations along these lines can happen frequently with algorithms that involve hashing (such as some associative array implementations), particularly if a slow hash function such as SHA2 is being used. Which is why for small collections of elements searching a simple array to see if it contains an element might be faster than searching a hash table, even though searching an array is O(N) and searching a hash set is O(1).

Question 4

Yes, it is simple, but your calculation is wrong.

What you have calculated is a linear growth, e.g. something of growth of O(n) e.g. if some input takes five minutes, you double the size of your input, then time spend is twice that time. You state that your algorithm run in O(n^2) which is exponential growth.

So your calculation would look like this:

M^2 = 5 minutes <=> 
M = sqrt(5) = 2.23607 (approx)

so

(4M)^2 = (4*2.23607)^2 = 80 minutes

Which is exponential growth.

This is also why you never talk about specific run times in computer science. Whether something takes 5 minutes or 5 hours is not interesting. What is interesting is what happens when we change the size of the input. Because when we implement algorithms we want something that runs faster, no matter what computer is used for testing when the size of the input moves towards infinite.

Question 5

Your guess is correct in case you have O(n), but we have O(n^2) which means you need to square the constant

T(M) = (M)^2 = M^2 = 5 minutes

T(4M) = (4 * M)^2 = 4^2 * M^2 = 16 * M^2

Substitute: M^2 = 5 minutes

T(4M) = 16 * M^2 = 16 * 5 minutes

T(4M) = 80 minutes