• Post Reply Bookmark Topic Watch Topic
  • New Topic

What math should I review if I am to understand Big-O notation  RSS feed

 
Ranch Hand
Posts: 175
1
Java Netbeans IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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!

 
Saloon Keeper
Posts: 7993
143
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Sheriff
Posts: 22845
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Naziru Gelajo
Ranch Hand
Posts: 175
1
Java Netbeans IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Lol I'm a computer science student though gentlemen. I noticed how some of the functions use logarithms. Should I review logs?
 
Stephan van Hulst
Saloon Keeper
Posts: 7993
143
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Paul Clapham
Sheriff
Posts: 22845
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephan van Hulst wrote:I think as long as you know what a logarithm is, it's good enough.


Yes, knowing the relationship between logarithms and exponentials should pretty much cover it.
 
Bartender
Posts: 3648
16
Firefox Browser Java Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Back in the college days, the "typical" prereq if any is usually a "discrete math" or abstract math course teaching induction, proofs, predicate logic and stuff.

 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!