5 ms·

I understand Big O. My point is for a lot of cases it doesn't matter, and just because someone can't throw off the top of their head the O complexity of some a

by boyter 13y ago

I understand Big O. My point is for a lot of cases it doesn't matter, and just because someone can't throw off the top of their head the O complexity of some algorithm they just wrote in a stressful interview does not mean they don't understand the concepts. Besides a O(N log N) algorithm over 10 or 100 items is not going to cause any issues. In the case of your standard CRUD application that's what you are going to be dealing with.

mseebach 13y ago
You're right that it matters very little if you can deduce the exact complexity right off the bat. But it DOES matter is if you can tell if an algorithm is closer to n^2 than log n. OR identify that n is low enough that it doesn't matter. > Besides a O(N log N) algorithm over 10 or 100 items is not going to cause any issues. In the case of your standard CRUD application that's what you are going to be dealing with. I think you mean n^2. n log n is generally considered pretty decent. But you're wrong, I know from experience that simple CRUD apps can suffer from grindingly poor performance, caused by, let's say, optimistic assertions of data volumes.
- boyter 13y ago
  Going to have to ask for an example. I am yet to have seen a basic CRUD app that had performance issues due to a bad coding algorithm. Certainly from poor queries but never from an bad algorithm. Keep in mind I would say that a simple CRUD app with millions of entries is no longer a simple CRUD app.
  - yuliyp 13y ago
    What does "poor queries" mean other than queries with poor asymptotic complexity based on the query plan?
    - boyter 13y ago
      Doing something like the following would classify as a poor query in my book with a very simple query plan, select * from table;
      - yuliyp 13y ago
        The query plan for that is simple, but the number of bytes transmitted per query is O(size of table) (as is the disk IO on the DB), which should clearly set off a red flag if you know that size of table can get large. You don't need a large exponent; You need to understand the rough cardinality of values, then you need to look at asymptotic complexity.
  - mseebach 13y ago
    So, the problem with your exclusion of "non-simple CRUD apps" is that simple CRUD apps have a nasty habit of ceasing to be simple. But yeah, case in point: I ran a small BB-style web forum a number of years ago. As it grew larger (on the order of 10k posts - hardly earth shattering for a web forum), the load on the server got unsustainable, and the page loads were really slow. It turned out that the algorithm to decide if a user had seen a post was to maintain a list of seen post IDs for each user, and compare them at each page view. For active users, the number of seen posts obviously approaches the number of posts: n^2.
  - brown9-2 13y ago
    A very easy, common example: given two lists of objects (from a database most likely), find the set of objects contained in both lists. The naive solution is a double for loop over each collection.

by boyter 13y ago

mseebach 13y ago

You're right that it matters very little if you can deduce the exact complexity right off the bat. But it DOES matter is if you can tell if an algorithm is closer to n^2 than log n. OR identify that n is low enough that it doesn't matter. > Besides a O(N log N) algorithm over 10 or 100 items is not going to cause any issues. In the case of your standard CRUD application that's what you are going to be dealing with. I think you mean n^2. n log n is generally considered pretty decent. But you're wrong, I know from experience that simple CRUD apps can suffer from grindingly poor performance, caused by, let's say, optimistic assertions of data volumes.

boyter 13y ago
Going to have to ask for an example. I am yet to have seen a basic CRUD app that had performance issues due to a bad coding algorithm. Certainly from poor queries but never from an bad algorithm. Keep in mind I would say that a simple CRUD app with millions of entries is no longer a simple CRUD app.
- yuliyp 13y ago
  What does "poor queries" mean other than queries with poor asymptotic complexity based on the query plan?
  - boyter 13y ago
    Doing something like the following would classify as a poor query in my book with a very simple query plan, select * from table;
    - yuliyp 13y ago
      The query plan for that is simple, but the number of bytes transmitted per query is O(size of table) (as is the disk IO on the DB), which should clearly set off a red flag if you know that size of table can get large. You don't need a large exponent; You need to understand the rough cardinality of values, then you need to look at asymptotic complexity.
- mseebach 13y ago
  So, the problem with your exclusion of "non-simple CRUD apps" is that simple CRUD apps have a nasty habit of ceasing to be simple. But yeah, case in point: I ran a small BB-style web forum a number of years ago. As it grew larger (on the order of 10k posts - hardly earth shattering for a web forum), the load on the server got unsustainable, and the page loads were really slow. It turned out that the algorithm to decide if a user had seen a post was to maintain a list of seen post IDs for each user, and compare them at each page view. For active users, the number of seen posts obviously approaches the number of posts: n^2.
- brown9-2 13y ago
  A very easy, common example: given two lists of objects (from a database most likely), find the set of objects contained in both lists. The naive solution is a double for loop over each collection.