Running time analysis on computing the largest factor of an integer using Euler's subtraction-based algorithm
It seems the algorithm tries to calculate n-1 gcd's simultaneously, and performs n-1 operations as long as one of the gcd's is not found. And since at least one gcd (gcd (n, 1)) takes n iterations, it is $\Theta (n^2)$. 

Of course that is just due to the stupid implementation, but probably a good example for estimating the runtime of an algorithm, not the runtime of a problem.

You need to show that $n^2$ is not $o(n log^k n)$ for any k.