posted 1 year ago

Greetings fellow Computer Scientists and programmers,

I am about to take a Data Structures & Algorithms class in Java, and I wanted to know what kind of math I should brush up on in order to understand the concepts of Big-O notation and the algorithms associated with. I am aware of some logarithmic algorithms as well as linear, so just wanted to know what field of math I should brush up on so I don't mess up in that class. Thanks!

I am about to take a Data Structures & Algorithms class in Java, and I wanted to know what kind of math I should brush up on in order to understand the concepts of Big-O notation and the algorithms associated with. I am aware of some logarithmic algorithms as well as linear, so just wanted to know what field of math I should brush up on so I don't mess up in that class. Thanks!

posted 1 year ago

The related math will likely also be taught in that class. If not, then calculus is probably the most related field, because you'll be comparing how functions behave for sufficiently large input variables.

*The mind is a strange and wonderful thing. I'm not sure that it will ever be able to figure itself out, everything else, maybe. From the atom to the universe, everything, except itself.*

posted 1 year ago

When I taught this topic to university math students, there weren't really any prerequisites for it. Not even calculus, really. Although the basic principle requires understanding how various functions behave as they approach infinity, that's different from the limit behaviour used in calculus.

I should say, though, that my students had difficulty understanding the big-O notation even though they were studying calculus. I got the impression that the idea that 2N and 36N were both O(N) functions and should be treated as equivalent went against the grain for math students. Many of my students were only in the class because Math 1 was a required course for all kinds of sciences, so maybe biology students would be better at the big-O notation? But I never thought to ask that question at the time.

I should say, though, that my students had difficulty understanding the big-O notation even though they were studying calculus. I got the impression that the idea that 2N and 36N were both O(N) functions and should be treated as equivalent went against the grain for math students. Many of my students were only in the class because Math 1 was a required course for all kinds of sciences, so maybe biology students would be better at the big-O notation? But I never thought to ask that question at the time.

Stephan van Hulst

Saloon Keeper

Posts: 7993

143

posted 1 year ago

I think as long as you know what a logarithm is, it's good enough.

If you can describe finding the solution to a problem (an algorithm) as finding the correct path in a tree of solutions, then that algorithm has logarithmic complexity.

If you can describe finding the solution to a problem (an algorithm) as finding the correct path in a tree of solutions, then that algorithm has logarithmic complexity.

It is sorta covered in the JavaRanch Style Guide. |