21–30 of 101 posts
>"My rule of thumb here is that if I have to use a loop within a loop, that’s O(n^2)." This might potentially do someone a disservice. The whole point of analysis is just that - to "analyze" the runtime and not resort to "rules of thumb." The presence of nested for loops itself is not a good reason to declare something quadratic. Consider the following which is most certainly not O(N^2): for (int i = 0; i for (int j…
(Warning: nerd sniping incoming) The main problem with this article is that it doesn't stress (or even mention, as far as I can tell) that it's performance characteristics at the margins . Meaning, it's about a generalized operation on a very large data set. Your fancy hashing algorithm might be slower than just doing a linear scan over a 10-element table, not to mention the maintenance of your tree structure. In the…
NO. BIG O notation is not average unless specified as such! It is an equivalence class of the provable upper bound on the execution time of the algorithm on an arbitrary input. There are algorithms like quick sort where average runtime != “big O of quicksort”
(yes this is a stupid contrived example, and I know one can make any case when one can make up any reality etc. - but I think it's a valid style figure in this case, to contrast the theoretical definition with the application).
Would you toss out that search algorithm and say 'well we have algorithms that search in better than O(n) so forget about this one'? No, you'd do 'if (container.size() == 50) { return container.bisect_find(key); } else { container.lalaland_find(key); } And that's exactly the difference between the theoretical concept and the application.
(although I'll admit that I started out writing the comment trying really hard to avoid the word 'average' because it's so confusing and then it still slipped in)
My experience, as someone who isn't a professional full-time developer (systems engineer / devops focused), but who personally geeks out on CS theory, is I find it fairly rare for developers that I work with that think of Big O considerations when writing their code. A prime example, was a piece of code that has to process incoming results that get stuck in a transnational database table. Instead of selecting, then p…
" is I find it fairly rare for developers that I work with that think of Big O considerations when writing their code." Do you mean that as in 'people I work with don't care about this, therefore it's not necessary' or as in 'people I work with are clowns who don't even know foundations'? Because (I think) I'm seeing replies to your post interpreting it both ways.
>"My rule of thumb here is that if I have to use a loop within a loop, that’s O(n^2)." This might potentially do someone a disservice. The whole point of analysis is just that - to "analyze" the runtime and not resort to "rules of thumb." The presence of nested for loops itself is not a good reason to declare something quadratic. Consider the following which is most certainly not O(N^2): for (int i = 0; i for (int j…
if for (int i = 0; i for (int i = 0; i If also for (int j = 1000; j >= 1; j = j / 2) were instead
for (int j = n; j >= 1; j = j / 2) - Then you'd have O(n log n)
OR for (int j = n; j >= 1; j -= 1) - O(n^2)
OR for (int j = n * 1000; j >= 1; j -= 1) - this is STILL O(n^2)
>"My rule of thumb here is that if I have to use a loop within a loop, that’s O(n^2)." This might potentially do someone a disservice. The whole point of analysis is just that - to "analyze" the runtime and not resort to "rules of thumb." The presence of nested for loops itself is not a good reason to declare something quadratic. Consider the following which is most certainly not O(N^2): for (int i = 0; i for (int j…
Well, as written, it is 'O(1)'. Or did you mean to put N instead of 1000?
My experience, as someone who isn't a professional full-time developer (systems engineer / devops focused), but who personally geeks out on CS theory, is I find it fairly rare for developers that I work with that think of Big O considerations when writing their code. A prime example, was a piece of code that has to process incoming results that get stuck in a transnational database table. Instead of selecting, then p…
Sounds like a communication problem to me. Non-academic developers might not know "Big O notation". But they absolutely know that nested loops are way less efficient than single loops. They know that some code performs better than other code. And while they might be writing inefficient code, that is an opportunity to talk to them and help them improve.
If you come at them with academic terms (right though you may be), and their eyes glaze over, try talking about the actual change you are seeking. Especially in the database world, as less experienced developers might not know that database performance can be tuned by how you use it. We all were new once. So educate them. Kindly.
Earlier quoted context omitted.
" is I find it fairly rare for developers that I work with that think of Big O considerations when writing their code." Do you mean that as in 'people I work with don't care about this, therefore it's not necessary' or as in 'people I work with are clowns who don't even know foundations'? Because (I think) I'm seeing replies to your post interpreting it both ways.
I wouldn't use the word clowns, because they are really good at other areas. In this case, the developers focus on a development environment that isn't widely used in the US, and I believe that they haven't had a formal CS education (more of the same type of self taught that I am).
Nah it was just an expression from my part, didn't mean to say that anyone not thinking about algorithmic complexity when writing any piece of software is a hack :)
(Warning: nerd sniping incoming) The main problem with this article is that it doesn't stress (or even mention, as far as I can tell) that it's performance characteristics at the margins . Meaning, it's about a generalized operation on a very large data set. Your fancy hashing algorithm might be slower than just doing a linear scan over a 10-element table, not to mention the maintenance of your tree structure. In the…
> What does happen is that on average, to find any title, you will need n / 2 operations (so not 1000, but 500, in this example - this part is plain wrong as it's written). You're conflating theta and omega notation for big O. Big O is the worst case scenario. The average or even typical operation doesn't matter. If the algorithm is the most complex when sorting a list of items that were already sorted in descending…
Big-O/theta/omega are all ways of categorizing functions. Those functions typically take as their argument some measure of the "size" of the input (which may be one variable or multiple). The output of the function could be:
* worst-case performance ("largest possible running time for all inputs of size N")
* average-case performance ("expected running time for an input of size N, chosen from some well-defined distribution")
* amortized performance ("largest possible running time among all possible sequences of N inputs, divided by N")
(We could also apply any of these definitions to something other than time, such as memory or I/O operations.)
For any of these definitions, we can talk about big-O, or big-theta, or big-omega in a well-defined way.
As an example, the worst-case time complexity of bubble sort is Ɵ(n^2). The average-case time complexity (assuming an input consisting of distinct elements, uniformly randomly permuted) is also Ɵ(n^2). Nevertheless, the best-case performance is Ɵ(n).
(Warning: nerd sniping incoming) The main problem with this article is that it doesn't stress (or even mention, as far as I can tell) that it's performance characteristics at the margins . Meaning, it's about a generalized operation on a very large data set. Your fancy hashing algorithm might be slower than just doing a linear scan over a 10-element table, not to mention the maintenance of your tree structure. In the…
> What does happen is that on average, to find any title, you will need n / 2 operations (so not 1000, but 500, in this example - this part is plain wrong as it's written). You're conflating theta and omega notation for big O. Big O is the worst case scenario. The average or even typical operation doesn't matter. If the algorithm is the most complex when sorting a list of items that were already sorted in descending…