6 ms·

Don't you want to know if your recipe takes 10 minutes or 10 hours to cook?

R_haterade 10y ago
Sometimes. Sometimes you just need to throw things in the oven until the first one browns up. I recently had a problem where I needed an adjacency matrix of shortest paths. It was a choice between dijkstra and floyd-warshall. My dijkstra implementation kicked the pants off of floyd warshall for this application by an order of magnitude, which you wouldn't really expect. And the big-O complexity was the same for both algorithms, it's just that for the graph structure, the operation count for dijkstra was much lower. It was the first one to brown up.
- bogomipz 10y ago
  Yes and its good to know the limits of Big O as you mentioned Big O tells you what an upper bound on something is but it will provide no answer as to which to which of two algorithms with the same upper bound will be faster. There is a field that deals with this and I watched some lectures by Robert Sedgewick called "Analytic Combinatorics" where he talks about a different analysis to do just that. He talks about being able to tell large institutional clients exactly how long an algorithm on a particular input will take and how important this was in the 1970s when computing power was much slower and far more expensive.
  - R_haterade 10y ago
    I will have to check this out as I'm in a lot of places where speed matters these days. Does he delve into the nuts and bolts of data structure for this, or does it stay more theoretical?
    - bogomipz 10y ago
      Its both. Here are some links: Video Lectures are here: https://www.coursera.org/learn/analysis-of-algorithms https://www.coursera.org/learn/analysis-of-algorithms and the book: http://aofa.cs.princeton.edu/home/ http://aofa.cs.princeton.edu/home/ Also a youtube - short history of algorithm analysis by Sedgewick is worth a watch: https://www.youtube.com/watch?v=qap2MyBTSZk https://www.youtube.com/watch?v=qap2MyBTSZk
- gk101 10y ago
  A few comments just in case this a critical part of your program, and if running it faster would help: 1. Using a heap with Dijkstra's algorithm would speed up your program From your comment I am guessing you are using Dijkstra's algorithm without a heap, which gives O(n * m) for one source, and O(n^2 * m) for all sources (all pairs shortest path), where n is the number of nodes/vertices, and m is the number of edges You would be able to improve that to O(m * n * lgn) by using a heap, which improves the time to run it by quite a lot in practice 2. The time it takes to run the program also depends on the density of your matrix: In the case where the graph is sparse: m ~ n, and will result in O(n^2 * lgn) (or O(n^3) without a heap) In the case where the graph is dense: m ~ n^2, and will result in O(n^3 * lgn) (or O(n^4) without a heap) Compare the numbers above to O(n^3), which is the time complexity of Floyd-Warshall So just in terms of time complexity, Floyd-Warshall would be faster in a dense graph
  - R_haterade 10y ago
    Agreed, but this was for a fast script that will probably run 100 times for analysis purposes--the code itself wasn't the end goal. I just needed something that could crunch my numbers in 10 minutes instead of 2 hours. :-)
  - R_haterade 10y ago
    I do want to express that I appreciate the effort you put into this post. Algorithms and data structures are my weakest point right now, and being able to read through your explanation is a helpful thing.
hellofunk 10y ago
That would be nice to know, but Big-O won't tell you that. It makes no time guarantees, it only provides an idea of an implementation. An O(1) algorithm sounds great, until you realize that 1 means 1 hour for that particular algorithm, while a competing algorithm's O(n) might mean n seconds in reality. What's in the parenthesis is not a measure of a unit of time, which is why Big-O fanatics often miss the bigger picture.
- tscs37 10y ago
  >An O(1) algorithm sounds great, until you realize that 1 means 1 hour for that particular algorithm, while a competing algorithm's O(n) might mean n seconds in reality. Well, I'm not trying to miss the bigger picture, but if you're going to scale that your O(n) algorithm will quickly take longer than a O(1) algorithm. I mean, let's just take a hashtable as example. This hash takes 1 hour to complete while you can search the list in milliseconds. But what if the list has billions and billions of entries and it takes longer than 1 hour? As some others said, Big-O is not something you use to choose one algorithm over the other, it's something you use to choose an algorithm that scales well and has acceptable performance. O(n) vs O(1) is a rather tame comparison, what if your competing algorithm is a O(n!) or worse?
guessmyname 10y ago
> Don't you want to know if your recipe takes 10 minutes or 10 hours to cook? Yes, the first time, then it becomes a skill learned from experience. I started learning Big-O a few months back and I have been working as a programmer for several years, not knowing about Big-O didn't stop me from becoming a lead of a development team. Knowing about Big-O is important but humans learn more from experience (aka. trail and error) than anything else. I started learning about Big-O just because I am interviewing right now and many tech companies love to ask those questions, but if I were not interviewing I would probably leave that topic for another time.
Anasufovic 10y ago
Yes, testing is critical.
e12e 10y ago
Rather, don't you want to know if that great dessert you ate, that took half an hour to prepare for 3 people, will be possible to make in an hour for a seating of 250 people? Because if it can't be done in an hour, you might have to pick something else to serve as dessert... (And we could probably turn this into a question about caching, by allowing you to prepare some of it a day early...)

Sometimes. Sometimes you just need to throw things in the oven until the first one browns up. I recently had a problem where I needed an adjacency matrix of shortest paths. It was a choice between dijkstra and floyd-warshall. My dijkstra implementation kicked the pants off of floyd warshall for this application by an order of magnitude, which you wouldn't really expect. And the big-O complexity was the same for both algorithms, it's just that for the graph structure, the operation count for dijkstra was much lower. It was the first one to brown up.

bogomipz 10y ago
Yes and its good to know the limits of Big O as you mentioned Big O tells you what an upper bound on something is but it will provide no answer as to which to which of two algorithms with the same upper bound will be faster. There is a field that deals with this and I watched some lectures by Robert Sedgewick called "Analytic Combinatorics" where he talks about a different analysis to do just that. He talks about being able to tell large institutional clients exactly how long an algorithm on a particular input will take and how important this was in the 1970s when computing power was much slower and far more expensive.
- R_haterade 10y ago
  I will have to check this out as I'm in a lot of places where speed matters these days. Does he delve into the nuts and bolts of data structure for this, or does it stay more theoretical?
  - bogomipz 10y ago
    Its both. Here are some links: Video Lectures are here: https://www.coursera.org/learn/analysis-of-algorithms https://www.coursera.org/learn/analysis-of-algorithms and the book: http://aofa.cs.princeton.edu/home/ http://aofa.cs.princeton.edu/home/ Also a youtube - short history of algorithm analysis by Sedgewick is worth a watch: https://www.youtube.com/watch?v=qap2MyBTSZk https://www.youtube.com/watch?v=qap2MyBTSZk
gk101 10y ago
A few comments just in case this a critical part of your program, and if running it faster would help: 1. Using a heap with Dijkstra's algorithm would speed up your program From your comment I am guessing you are using Dijkstra's algorithm without a heap, which gives O(n * m) for one source, and O(n^2 * m) for all sources (all pairs shortest path), where n is the number of nodes/vertices, and m is the number of edges You would be able to improve that to O(m * n * lgn) by using a heap, which improves the time to run it by quite a lot in practice 2. The time it takes to run the program also depends on the density of your matrix: In the case where the graph is sparse: m ~ n, and will result in O(n^2 * lgn) (or O(n^3) without a heap) In the case where the graph is dense: m ~ n^2, and will result in O(n^3 * lgn) (or O(n^4) without a heap) Compare the numbers above to O(n^3), which is the time complexity of Floyd-Warshall So just in terms of time complexity, Floyd-Warshall would be faster in a dense graph
- R_haterade 10y ago
  Agreed, but this was for a fast script that will probably run 100 times for analysis purposes--the code itself wasn't the end goal. I just needed something that could crunch my numbers in 10 minutes instead of 2 hours. :-)
- R_haterade 10y ago
  I do want to express that I appreciate the effort you put into this post. Algorithms and data structures are my weakest point right now, and being able to read through your explanation is a helpful thing.

hellofunk 10y ago

That would be nice to know, but Big-O won't tell you that. It makes no time guarantees, it only provides an idea of an implementation. An O(1) algorithm sounds great, until you realize that 1 means 1 hour for that particular algorithm, while a competing algorithm's O(n) might mean n seconds in reality. What's in the parenthesis is not a measure of a unit of time, which is why Big-O fanatics often miss the bigger picture.

tscs37 10y ago
>An O(1) algorithm sounds great, until you realize that 1 means 1 hour for that particular algorithm, while a competing algorithm's O(n) might mean n seconds in reality. Well, I'm not trying to miss the bigger picture, but if you're going to scale that your O(n) algorithm will quickly take longer than a O(1) algorithm. I mean, let's just take a hashtable as example. This hash takes 1 hour to complete while you can search the list in milliseconds. But what if the list has billions and billions of entries and it takes longer than 1 hour? As some others said, Big-O is not something you use to choose one algorithm over the other, it's something you use to choose an algorithm that scales well and has acceptable performance. O(n) vs O(1) is a rather tame comparison, what if your competing algorithm is a O(n!) or worse?

guessmyname 10y ago

> Don't you want to know if your recipe takes 10 minutes or 10 hours to cook? Yes, the first time, then it becomes a skill learned from experience. I started learning Big-O a few months back and I have been working as a programmer for several years, not knowing about Big-O didn't stop me from becoming a lead of a development team. Knowing about Big-O is important but humans learn more from experience (aka. trail and error) than anything else. I started learning about Big-O just because I am interviewing right now and many tech companies love to ask those questions, but if I were not interviewing I would probably leave that topic for another time.

Anasufovic 10y ago

Yes, testing is critical.

e12e 10y ago

Rather, don't you want to know if that great dessert you ate, that took half an hour to prepare for 3 people, will be possible to make in an hour for a seating of 250 people? Because if it can't be done in an hour, you might have to pick something else to serve as dessert... (And we could probably turn this into a question about caching, by allowing you to prepare some of it a day early...)