in Computer Science, how important is knowing Big-O?

Discussion in 'OT Technology' started by HardTech, Mar 22, 2006.

  1. HardTech

    HardTech hungry

    Joined:
    May 5, 2000
    Messages:
    28,103
    Likes Received:
    1
    Location:
    NorCal
    I got a Data Structures book from a professor (I'm in Information Systems, btw) who teaches Computer Science. I told him I wanted to learn more about CS, and he told me Data Structures are pretty much the bread and butter of CS.

    The very first chapter is Big-O, but it seemed so heavy with math, especially logarithms, I couldn't understand it. I'm sure with a few weeks of studying I could start getting a grasp of it, but when you're going higher education in CS, how important is knowing that?

    The rest of the book seemed easy, though.
     
  2. MrMan

    MrMan New Member

    Joined:
    Jul 13, 2004
    Messages:
    308
    Likes Received:
    0
    Big-O is usually used to determine the efficiency of algorithms. Usually, programmers just use known efficient algorithms. However, there are cases where a programmer would need to create their own algorithm, and then test if it is efficient. That's where Big-O comes in.

    Of course there are others ways to test efficiency, such as test runs, but Big-O is the theoretical approach to why an algorithm is efficient.
     
  3. HardTech

    HardTech hungry

    Joined:
    May 5, 2000
    Messages:
    28,103
    Likes Received:
    1
    Location:
    NorCal
    I can see where that's useful, but as a programmer, I've never had to rewrite an algorithm.

    Is that common?
     
  4. HardTech

    HardTech hungry

    Joined:
    May 5, 2000
    Messages:
    28,103
    Likes Received:
    1
    Location:
    NorCal
    also, it's impossible to know if an algorithm is mathematically the most efficient algorithm, right? If so, then there comes a time when you get diminishing results.
     
  5. deusexaethera

    deusexaethera OT Supporter

    Joined:
    Jan 27, 2005
    Messages:
    19,712
    Likes Received:
    0
    That would depend on whether there are an infinite number of possible algorithms to solve a given problem. Theoretically there are, but any sane person would rule out algorithms that are specifically concocted to be less efficient than the first algorithm they thought of. Meanwhile, there is always a minimum possible number of steps to accomplish a task, so I would say that for all practical purposes it IS possible to determine the most efficient algorithm for all but the most convoluted tasks.
     
  6. deusexaethera

    deusexaethera OT Supporter

    Joined:
    Jan 27, 2005
    Messages:
    19,712
    Likes Received:
    0
    (skims Wikipedia)

    After a quick refresher on what Big-O is, I would say that it isn't necessary to understand the concept in order to program. The bigger your programs get and the more experienced you become, the more important it will be to be able to look at your code and realize, for example, that a single recursive function call may replicate itself 10,000 times in the process of doing what initially appears to be a simple task because the code inside the function looks to be very small. That said, every programmer that has ever proofread their code and looked for ways to speed it up has developed an innate ability to sense the Big-O complexity of their code, so while it almost certainly helps to understand the math behind that intuition, it won't make a huge difference in your ability to write efficient algorithms in the real world.
     
  7. MrMan

    MrMan New Member

    Joined:
    Jul 13, 2004
    Messages:
    308
    Likes Received:
    0
    It's common for programmers to use already existing algorithms such as known searching, sorting...

    You can study an algorithm to see if it is more efficient than another algorithm. But some algorithms are better than others in certain cases.

    To clarify, (bad example for Big-O, good for algorithm better in some cases)
    A linear search is good if your target is near the front of an array. Also if your array isn't sorted in any way.

    A binary search is usually more efficient than a linear search (depending on location of target), but requires the array to be sorted.
     
    Last edited: Mar 22, 2006
  8. Penguin Man

    Penguin Man Protect Your Digital Liberties

    Joined:
    Apr 27, 2002
    Messages:
    21,696
    Likes Received:
    0
    Location:
    Edmonton, AB
    It is one of the fundamental parts of computer science. If you don't know how big-Oh notation works, and how to determine the complexity of an algorithm, you cannot truly call yourself a computer scientist.
     
  9. deusexaethera

    deusexaethera OT Supporter

    Joined:
    Jan 27, 2005
    Messages:
    19,712
    Likes Received:
    0
    Thus the distinction between computer scientist and computer programmer. I, for one, am a software engineer, which means I write specs and talk to customers and plan the shit out of everything so the programmers can't have any fun at all, but the product will work right.
     
  10. HardTech

    HardTech hungry

    Joined:
    May 5, 2000
    Messages:
    28,103
    Likes Received:
    1
    Location:
    NorCal
    I guess it doesn't come naturally.

    Unless you mean I can look at an algorithm and think "damn, that's complex!"
     
  11. Peyomp

    Peyomp New Member

    Joined:
    Jan 11, 2002
    Messages:
    14,017
    Likes Received:
    0
    I would say that a software engineer is a programmer who is capable of functioning in an enterprise where he must work together with others to create a cohesive design, documentation and implementation so that larger applications can be built successfully.

    There is punk-rock programming, and then there is software engineering. The skillset of the software engineer become important as the size of an application grows, but he's still a programmer. Although a system architect or user representative might not actually code, they damn well better be programmers.
     

Share This Page