patternMajor
Are there variations of the regular runtimes of the Big-O-Notation?
Viewed 0 times
variationstheareregularruntimesbignotationthere
Problem
There are multiple $O$-Notations, like $O(n)$ or $O(n^2)$ and so on. I was wondering, if there are variations of those in reality such as $O(2n^2)$ or $O(\log n^2)$, or if those are mathematically incorrect.
Or would it be a right thing to say that it is possible to improve a $O(5n^2)$ to a $O(3n^2)$? I can't and don't need to figure out runtimes yet and I do not need to improve anything, but I'd need to know if this how you describe your functions in reality.
Or would it be a right thing to say that it is possible to improve a $O(5n^2)$ to a $O(3n^2)$? I can't and don't need to figure out runtimes yet and I do not need to improve anything, but I'd need to know if this how you describe your functions in reality.
Solution
I was wondering, if there are variations of those in reality such as $O(2n^2)$ or $O(\log (n^2))$, or if those are mathematically incorrect.
Yes, $O(2n^2)$ or $O(\log (n^2))$ are valid variations.
However, you will see them rarely if you would see them at all, especially in the end results. The reason is that $O(2n^2)$ is $O(n^2)$. Similarly, $O(\log (n^2))$ is $O(\log n)$. That might be surprising to beginners. However, those equalities are more or less the very reason why big $O$-notations were introduced, to hide a multiplicative constant factor that is often hard to pin down and relatively insignificant.
Would it be a right thing to say that it is possible to improve a $O(5n^2)$ to a $O(3n^2)$?
It is not an improvement at all if the time-complexity of an algorithm is changed from $O(5n^2)$ to a $O(3n^2)$ or from $\Omega(5n^2)$ to $\Omega(3n^2)$, because $O(5n^2)$ is $O(3n^2)$ while $\Omega(5n^2)$ is $\Omega(3n^2)$. So it is incorrect to say the time-complexity is improved from $O(5n^2)$ to $O(3n^2)$. It is correct to say the time-complexity of an algorithm is improved from $5n^2$ to $3n^2$, of course.
Exercise 1. Show that $O(5n^2)=O(3n^2)=O(n^2)$.
Exercise 2. Show that $O(\log n)=O(\log (n^2))$.
Exercise 3. Show that $\Omega(n^2+n)=\Omega(n^2)$.
Yes, $O(2n^2)$ or $O(\log (n^2))$ are valid variations.
However, you will see them rarely if you would see them at all, especially in the end results. The reason is that $O(2n^2)$ is $O(n^2)$. Similarly, $O(\log (n^2))$ is $O(\log n)$. That might be surprising to beginners. However, those equalities are more or less the very reason why big $O$-notations were introduced, to hide a multiplicative constant factor that is often hard to pin down and relatively insignificant.
Would it be a right thing to say that it is possible to improve a $O(5n^2)$ to a $O(3n^2)$?
It is not an improvement at all if the time-complexity of an algorithm is changed from $O(5n^2)$ to a $O(3n^2)$ or from $\Omega(5n^2)$ to $\Omega(3n^2)$, because $O(5n^2)$ is $O(3n^2)$ while $\Omega(5n^2)$ is $\Omega(3n^2)$. So it is incorrect to say the time-complexity is improved from $O(5n^2)$ to $O(3n^2)$. It is correct to say the time-complexity of an algorithm is improved from $5n^2$ to $3n^2$, of course.
Exercise 1. Show that $O(5n^2)=O(3n^2)=O(n^2)$.
Exercise 2. Show that $O(\log n)=O(\log (n^2))$.
Exercise 3. Show that $\Omega(n^2+n)=\Omega(n^2)$.
Context
StackExchange Computer Science Q#109127, answer score: 21
Revisions (0)
No revisions yet.