When you start applying real numbers to n, using O() doesn't make sense. When comparing the two in a slightly practical sense, the constant factor has to be taken into account.

If I understand correctly, in this case you can directly compare them - the algorithm is the same, so the constant factors are the same.

However, this is in so many ways not my field, so I could easily have completely misunderstood.

You do not understand correctly. Compare the ratio of the quadratic f(n) = 1E100 + n2 to the linear g(n) = 1E100 + n. Using n=100 and n=1000 the ratio is effectively 1.0. You need to get to n=100000000000000000000000000000000000000000000000000 before the ratio is 2.

I see your point - we can compare the powers that n is raised to, but without knowing the constant factor we can't know the proportion of the result that it is responsible for.

Except that this algorithm can't be used for anything as small as n = 100. Essentially the analysis is asymptotic, meaning that you have matrices of dimension n = q^N and let N tend towards infinity to get your bound on omega.