Big O notation (Maybe offtopic)

C

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.
 
?

=?ISO-8859-1?Q?Stefan_N=E4we?=

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
 
D

David

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
 
R

Richard Herring

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).
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top