Big O notation (Maybe offtopic)

Discussion in 'C++' started by codefixer@gmail.com, Aug 18, 2005.

  1. Guest

    Hello:

    I have seen that many interviewers ask, so what is the Big O for that
    algorithm (say Binary Search) which is o(log n) + 1 (in most cases).

    I know what is the Big O for most algorithms, but I am wondering how
    can one derive the same ? I want to know if any places on the web have
    concrete proof or methodology to do so.

    Because of this Big O I have almost failed in an interview but my
    conscience refused to answer the question by memorization as I really
    don't know how to derive it mathematically.

    Sorry I am unable to afford a Data Structure course or buy expensive
    books. So if you know any good links kindly share else ignore this
    e-mail.

    Sorry for the spam if it's offtopic.

    Thanks you.
    , Aug 18, 2005
    #1
    1. Advertising

  2. wrote:
    > Hello:
    >
    > I have seen that many interviewers ask, so what is the Big O for that
    > algorithm (say Binary Search) which is o(log n) + 1 (in most cases).
    >
    > I know what is the Big O for most algorithms, but I am wondering how
    > can one derive the same ? I want to know if any places on the web have
    > concrete proof or methodology to do so.
    >
    > Because of this Big O I have almost failed in an interview but my
    > conscience refused to answer the question by memorization as I really
    > don't know how to derive it mathematically.
    >
    > Sorry I am unable to afford a Data Structure course or buy expensive
    > books. So if you know any good links kindly share else ignore this
    > e-mail.
    >
    > Sorry for the spam if it's offtopic.
    >
    > Thanks you.
    >


    http://en.wikipedia.org/wiki/Big_O_notation
    =?ISO-8859-1?Q?Stefan_N=E4we?=, Aug 18, 2005
    #2
    1. Advertising

  3. David Guest

    On Thu, 18 Aug 2005 04:20:52 UTC, wrote:

    > Hello:
    >
    > I have seen that many interviewers ask, so what is the Big O for that
    > algorithm (say Binary Search) which is o(log n) + 1 (in most cases).
    >
    > I know what is the Big O for most algorithms, but I am wondering how
    > can one derive the same ? I want to know if any places on the web have
    > concrete proof or methodology to do so.
    >
    > Because of this Big O I have almost failed in an interview but my
    > conscience refused to answer the question by memorization as I really
    > don't know how to derive it mathematically.
    >
    > Sorry I am unable to afford a Data Structure course or buy expensive
    > books. So if you know any good links kindly share else ignore this
    > e-mail.
    >
    > Sorry for the spam if it's offtopic.
    >
    > Thanks you.


    Hello,

    Someone else has pointed out a link. Basically, Big O Notation is
    just a way of expressing the complexity of a problem in terms of what
    one thinks are the expensive operations of an algorithm. It is usually
    expressed in the number of records or items that need to be processed.

    Memorization is good to some degree. You won't have time to derive
    the complexity for every task that you decide to check, so being able
    to classify the problem is helpful. On the other hand, it is good
    that you want to understand what the notation means and how it can be
    helpful to you and your team.

    David
    David, Aug 18, 2005
    #3
  4. In message <>,
    writes
    >Hello:
    >
    >I have seen that many interviewers ask, so what is the Big O for that
    >algorithm (say Binary Search) which is o(log n) + 1 (in most cases).


    O-notation is about the limit as n tends to infinity. log(n) grows
    faster than any constant, so adding 1 is meaningless. It's just
    O(log(n)).
    >
    >I know what is the Big O for most algorithms, but I am wondering how
    >can one derive the same ? I want to know if any places on the web have
    >concrete proof or methodology to do so.
    >
    >Because of this Big O I have almost failed in an interview but my
    >conscience refused to answer the question by memorization as I really
    >don't know how to derive it mathematically.


    Just estimate the number of operations, considering the "average" case.
    For example, binary search: each pass makes one comparison and on
    average it halves the number of items to be searched, so the question is
    really "how many times do I have to divide n by 2 to get 1?" In
    mathematical terms, you're solving n/2^x = 1, and the answer is x =
    log_2(n).

    > Sorry I am unable to afford a Data Structure course or buy expensive
    >books. So if you know any good links kindly share else ignore this
    >e-mail.
    >
    >Sorry for the spam if it's offtopic.
    >
    >Thanks you.
    >


    --
    Richard Herring
    Richard Herring, Aug 18, 2005
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Grey Squirrel

    Hungarian Notation Vs. Pascal Notation?

    Grey Squirrel, Mar 19, 2007, in forum: ASP .Net
    Replies:
    6
    Views:
    1,272
    Steve C. Orr [MCSD, MVP, CSM, ASP Insider]
    Mar 21, 2007
  2. Shaguf
    Replies:
    0
    Views:
    329
    Shaguf
    Dec 24, 2008
  3. Shaguf
    Replies:
    0
    Views:
    432
    Shaguf
    Dec 26, 2008
  4. Shaguf
    Replies:
    0
    Views:
    219
    Shaguf
    Dec 26, 2008
  5. Shaguf
    Replies:
    0
    Views:
    202
    Shaguf
    Dec 24, 2008
Loading...

Share This Page