• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

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

 
Ranch Hand
Posts: 186
1
Netbeans IDE Java Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 15510
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
Marshal
Posts: 28193
95
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 186
1
Netbeans IDE Java Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 15510
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Marshal
Posts: 28193
95
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Android Mac OS X Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.

 
Consider Paul's rocket mass heater.
reply
    Bookmark Topic Watch Topic
  • New Topic