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

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

1. ### HardTechhungry

Joined:
May 5, 2000
Messages:
28,103
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. ### MrManNew Member

Joined:
Jul 13, 2004
Messages:
308
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. ### HardTechhungry

Joined:
May 5, 2000
Messages:
28,103
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. ### HardTechhungry

Joined:
May 5, 2000
Messages:
28,103
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. ### deusexaetheraOT Supporter

Joined:
Jan 27, 2005
Messages:
19,712
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. ### deusexaetheraOT Supporter

Joined:
Jan 27, 2005
Messages:
19,712
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. ### MrManNew Member

Joined:
Jul 13, 2004
Messages:
308
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 ManProtect Your Digital Liberties

Joined:
Apr 27, 2002
Messages:
21,696
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. ### deusexaetheraOT Supporter

Joined:
Jan 27, 2005
Messages:
19,712
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. ### HardTechhungry

Joined:
May 5, 2000
Messages:
28,103
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!"

Joined:
Jan 11, 2002
Messages:
14,017