dcsimg
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 9 of 9

Thread: Big-O Notation

  1. #1
    Join Date
    Mar 2011
    Posts
    52

    Big-O Notation

    I am just starting a software engineer degree and I want to learn Big-O notation a head of time. I am trying to do all I can to get ahead before I actually start my programming classes. Do any of you recommend a very well explained website or book to learn Big-O notation? Other than Big-O and general programming basics(Declaring variables, operators, basic class structure, basic pointers, exploring library's ,passing variables) what do you recommend to learn ahead of time? I really am taking programming seriously and want to do the best I can. I can't think of a better way of doing this than asking professionals what they wish they had spent more time on before they went to school or at least what would have made school much easier is they had known.

    I will make a list of all things you mention and try to go over all of them so your time responding will not be a waist. I thank all of you in advance.

    one last note:
    in an earlier post I was told to learn an API. I really do not feel I am at that level. Am I making it seem harder than it is? I know it will take time and I am not worried about that my question is it seems I need to know more than I do now to learn an API, is this correct? or do the concepts just take time to learn not a vast understanding of c++?

  2. #2
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Location
    Florida
    Posts
    12,554

    Re: Big-O Notation

    While something you eventually need to be aware of, Big O isn't really a topic for beginners. It's a way of measuring performance of algorithms and data structures and without knowledge of how those algorithms and data structures work, learning about their performance won't mean anything to you.

    Just get a beginner's tutorial in the language of your choice and work through that first.

  3. #3
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Seattle, WA
    Posts
    10,895

    Re: Big-O Notation

    When they first start discussing big-O, they always do it in purely mathematical terms which inevitably make the concept seem more difficult than it is.

    Sure, you define it in terms of a relation between functions on the limit as x goes to infinity. But proving that sort of relationship can be a pain. It's much easier to just understand what big-O means on an intuitive level.

    The graph of a function which is O(n) will be a straight line, The graph of a function which is O(n^2) will be part of a parabola, etc. An algorithm which is O(n log n) or less is very efficient, an algorithm which is O(n^2) or worse is tolerable in a pinch, and an algorithm which is O(m^n) for some constant m (otherwise known as "NP-Hard") is unacceptable in most cases.

    The majority of today's algorithmic research is in trying to find good "polynomial time", or O(n^ small m) approximation algorithms for problems whose exact solution would be NP-Hard.

  4. #4
    Join Date
    Mar 2011
    Posts
    52

    Re: Big-O Notation

    I "think" I understand the concept that Big-O stands for. Each symbol represents parts of a algorithm to the power of times it has to be ran or looped. I know that time is also included. Algorithms and data structure is my second class and I just wanted to get ahead. I know this has to be covered. I am also trying to work on using class templates. Overall my approach is if I keep learning these new concepts(new to me) and apply them in simple programs to where I understand the basics of how they work I will get ahead for school and they will teach me how to implement and refine my coding.

    Big-O seems like a very important aspect of programming. Choosing the fastest and most productive method of processing data. My workplace now has very slow programs that where just coded a few months ago. I bet those programmers couldn't tell ya much about Big-O lol. I am no one to judge at this current time but something is not right.

  5. #5
    Join Date
    Mar 2011
    Posts
    52

    Re: Big-O Notation

    Thank you GCDEF,
    I know this may be a little past me but as stated above if I can understand it I would like to at the least look over it and get the concept. I have been looking through this forum at questions posted by students and trying to figure them out on my own. I believe this is a great way to get to work on problems that may arise in college. I love beginner tutorials and work on them as much as I can, along with looking up things I have not learned and writing a simple program to use them. I finally figured out reading by itself was not teaching me anything. If I read how to do something then write a simple program to use it I seem to remember it 100% better. I do not wont to try to learn it all in a day I know it will take time and I am ready to take that time to do it right. Just trying to figure out what the best way to approach this is.


    thanks Lindley but I really need to read something that will break it down for me. I thought one of you might have a link or book that was a great deal of help to you when you learned it. I will keep searching for the info.
    Last edited by josh26757; April 6th, 2011 at 09:52 AM.

  6. #6
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Seattle, WA
    Posts
    10,895

    Re: Big-O Notation

    The motivation behind big-O is to describe the speed of an algorithm in terms that are independent of the particular architecture it is run on. So the speed of the computer you're using for testing does not influence the choice of algorithm too much.

  7. #7
    Join Date
    Mar 2011
    Posts
    52

    Re: Big-O Notation

    Lindley,
    I see what your saying. Perhaps a way to compare something like a recursive call to using a loop that both have the same outcome. My understanding of it is comparing methods of coding with the same outcome. Say searching a very big container from start to finish versus binary search.

  8. #8
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Seattle, WA
    Posts
    10,895

    Re: Big-O Notation

    That's more or less it, yes.

  9. #9
    Join Date
    Mar 2011
    Posts
    52

    Re: Big-O Notation

    Thank you for your time!

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)