Skip to main content
deleted 15 characters in body
Source Link
3yakuya
  • 934
  • 6
  • 17

I believe the text you quoted is quite inacurrate (using the word "better" is usually meaningless unless you provide the context: in terms of time, space etc.) Anyway, I believe the simplest explanation would be:

If time of execution grows with the size of an input then it is definitely not $O(1)$ and that should be clear. $O(1)$ does not mean fast. It just means (in terms of time complexity) that time of execution is nothas a function of the size of an inputconstant upper bound.

Now, let's take a relatively small set of 10 elements and have a few algorithms to sort it (just an example). Let's assume that we keep the elements in a structure that also provides us with an algorithm capable of sorting the elements in constant time. Let's say our sorting-algorithms can have following complexities (with big-O notation):

  1. $O(1)$
  2. $O(n)$
  3. $O(nlog(n))$
  4. $O(n^2)$

Which algoritm would you choose? The first answer that comes to mind may be "of course I'll use the $O(1)$ one!", but this is not necessarily correct. What you forget when thinking like that is that the big-O notation hides the constant factor. And if you know your set is pretty small, then this constant factor may be much more important than the asympthotic complexity.

Now let's "reveal" the true complexities of that sorting algorithms mentioned above (where "true" means not hiding the constant), represented by numbers of steps required to finish (and assume all steps take the same amount of time):

  1. $200$ steps
  2. $11n$ steps
  3. $4nlog(n)$ steps (log with base 2)
  4. $1n^2$ steps

If our input is of size 10, then these are exact amounts of steps for every algorithm mentioned above:

  1. $200$ steps
  2. $11 \times 10 = 110$ steps
  3. $4 \times 10 \times 3.32 \approx 134$ steps
  4. $1 \times 100 = 100$ steps

As you see, in this case the apparently worst algorithm with asympthotic complexity $O(n^2)$ is the fastest one, beating algorithms with $O(1), O(n)$ and $O(nlog(n))$ asympthotic complexities. The constant factor hidden by the big-O notation matters here. In my opinion it does not mean that we can treat $O(n^2)$ as better than $O(1)$ (what would it mean anyway?) It means that for sufficiently small input (like you've seen in the example) the $O(n^2)$ may still be faster than $O(1)$ because of the hidden constant. And if the constant is relatively large compared to the size of the input, it may matter more than the asympthotic complexity.

I believe the text you quoted is quite inacurrate (using the word "better" is usually meaningless unless you provide the context: in terms of time, space etc.) Anyway, I believe the simplest explanation would be:

If time of execution grows with the size of an input then it is definitely not $O(1)$ and that should be clear. $O(1)$ does not mean fast. It just means (in terms of time complexity) that time of execution is not a function of the size of an input.

Now, let's take a relatively small set of 10 elements and have a few algorithms to sort it (just an example). Let's assume that we keep the elements in a structure that also provides us with an algorithm capable of sorting the elements in constant time. Let's say our sorting-algorithms can have following complexities (with big-O notation):

  1. $O(1)$
  2. $O(n)$
  3. $O(nlog(n))$
  4. $O(n^2)$

Which algoritm would you choose? The first answer that comes to mind may be "of course I'll use the $O(1)$ one!", but this is not necessarily correct. What you forget when thinking like that is that the big-O notation hides the constant factor. And if you know your set is pretty small, then this constant factor may be much more important than the asympthotic complexity.

Now let's "reveal" the true complexities of that sorting algorithms mentioned above (where "true" means not hiding the constant), represented by numbers of steps required to finish (and assume all steps take the same amount of time):

  1. $200$ steps
  2. $11n$ steps
  3. $4nlog(n)$ steps (log with base 2)
  4. $1n^2$ steps

If our input is of size 10, then these are exact amounts of steps for every algorithm mentioned above:

  1. $200$ steps
  2. $11 \times 10 = 110$ steps
  3. $4 \times 10 \times 3.32 \approx 134$ steps
  4. $1 \times 100 = 100$ steps

As you see, in this case the apparently worst algorithm with asympthotic complexity $O(n^2)$ is the fastest one, beating algorithms with $O(1), O(n)$ and $O(nlog(n))$ asympthotic complexities. The constant factor hidden by the big-O notation matters here. In my opinion it does not mean that we can treat $O(n^2)$ as better than $O(1)$ (what would it mean anyway?) It means that for sufficiently small input (like you've seen in the example) the $O(n^2)$ may still be faster than $O(1)$ because of the hidden constant. And if the constant is relatively large compared to the size of the input, it may matter more than the asympthotic complexity.

I believe the text you quoted is quite inacurrate (using the word "better" is usually meaningless unless you provide the context: in terms of time, space etc.) Anyway, I believe the simplest explanation would be:

If time of execution grows with the size of an input then it is definitely not $O(1)$ and that should be clear. $O(1)$ does not mean fast. It just means (in terms of time complexity) that time of execution has a constant upper bound.

Now, let's take a relatively small set of 10 elements and have a few algorithms to sort it (just an example). Let's assume that we keep the elements in a structure that also provides us with an algorithm capable of sorting the elements in constant time. Let's say our sorting-algorithms can have following complexities (with big-O notation):

  1. $O(1)$
  2. $O(n)$
  3. $O(nlog(n))$
  4. $O(n^2)$

Which algoritm would you choose? The first answer that comes to mind may be "of course I'll use the $O(1)$ one!", but this is not necessarily correct. What you forget when thinking like that is that the big-O notation hides the constant factor. And if you know your set is pretty small, then this constant factor may be much more important than the asympthotic complexity.

Now let's "reveal" the true complexities of that sorting algorithms mentioned above (where "true" means not hiding the constant), represented by numbers of steps required to finish (and assume all steps take the same amount of time):

  1. $200$ steps
  2. $11n$ steps
  3. $4nlog(n)$ steps (log with base 2)
  4. $1n^2$ steps

If our input is of size 10, then these are exact amounts of steps for every algorithm mentioned above:

  1. $200$ steps
  2. $11 \times 10 = 110$ steps
  3. $4 \times 10 \times 3.32 \approx 134$ steps
  4. $1 \times 100 = 100$ steps

As you see, in this case the apparently worst algorithm with asympthotic complexity $O(n^2)$ is the fastest one, beating algorithms with $O(1), O(n)$ and $O(nlog(n))$ asympthotic complexities. The constant factor hidden by the big-O notation matters here. In my opinion it does not mean that we can treat $O(n^2)$ as better than $O(1)$ (what would it mean anyway?) It means that for sufficiently small input (like you've seen in the example) the $O(n^2)$ may still be faster than $O(1)$ because of the hidden constant. And if the constant is relatively large compared to the size of the input, it may matter more than the asympthotic complexity.

Source Link
3yakuya
  • 934
  • 6
  • 17

I believe the text you quoted is quite inacurrate (using the word "better" is usually meaningless unless you provide the context: in terms of time, space etc.) Anyway, I believe the simplest explanation would be:

If time of execution grows with the size of an input then it is definitely not $O(1)$ and that should be clear. $O(1)$ does not mean fast. It just means (in terms of time complexity) that time of execution is not a function of the size of an input.

Now, let's take a relatively small set of 10 elements and have a few algorithms to sort it (just an example). Let's assume that we keep the elements in a structure that also provides us with an algorithm capable of sorting the elements in constant time. Let's say our sorting-algorithms can have following complexities (with big-O notation):

  1. $O(1)$
  2. $O(n)$
  3. $O(nlog(n))$
  4. $O(n^2)$

Which algoritm would you choose? The first answer that comes to mind may be "of course I'll use the $O(1)$ one!", but this is not necessarily correct. What you forget when thinking like that is that the big-O notation hides the constant factor. And if you know your set is pretty small, then this constant factor may be much more important than the asympthotic complexity.

Now let's "reveal" the true complexities of that sorting algorithms mentioned above (where "true" means not hiding the constant), represented by numbers of steps required to finish (and assume all steps take the same amount of time):

  1. $200$ steps
  2. $11n$ steps
  3. $4nlog(n)$ steps (log with base 2)
  4. $1n^2$ steps

If our input is of size 10, then these are exact amounts of steps for every algorithm mentioned above:

  1. $200$ steps
  2. $11 \times 10 = 110$ steps
  3. $4 \times 10 \times 3.32 \approx 134$ steps
  4. $1 \times 100 = 100$ steps

As you see, in this case the apparently worst algorithm with asympthotic complexity $O(n^2)$ is the fastest one, beating algorithms with $O(1), O(n)$ and $O(nlog(n))$ asympthotic complexities. The constant factor hidden by the big-O notation matters here. In my opinion it does not mean that we can treat $O(n^2)$ as better than $O(1)$ (what would it mean anyway?) It means that for sufficiently small input (like you've seen in the example) the $O(n^2)$ may still be faster than $O(1)$ because of the hidden constant. And if the constant is relatively large compared to the size of the input, it may matter more than the asympthotic complexity.