Big O notation (Maybe offtopic)

[codefixer]

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.

[Stefan Näwe]

co*******@gmail.com 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

[David]

On Thu, 18 Aug 2005 04:20:52 UTC, co*******@gmail.com 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

[Richard Herring]

In message <11**********************@f14g2000cwb.googlegroups .com>,
co*******@gmail.com 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