Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Big O notation (Maybe offtopic)

Reply
Thread Tools

Big O notation (Maybe offtopic)

 
 
codefixer@gmail.com
Guest
Posts: n/a
 
      08-18-2005
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.

 
Reply With Quote
 
 
 
 
=?ISO-8859-1?Q?Stefan_N=E4we?=
Guest
Posts: n/a
 
      08-18-2005
http://www.velocityreviews.com/forums/(E-Mail Removed) 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
 
Reply With Quote
 
 
 
 
David
Guest
Posts: n/a
 
      08-18-2005
On Thu, 18 Aug 2005 04:20:52 UTC, (E-Mail Removed) 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
 
Reply With Quote
 
Richard Herring
Guest
Posts: n/a
 
      08-18-2005
In message <(E-Mail Removed) .com>,
(E-Mail Removed) 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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
How to convert Infix notation to postfix notation Tameem C Programming 454 01-31-2014 06:01 PM
GIDS 2009 .Net:: Save Big, Win Big, Learn Big: Act Before Dec 29 2008 Shaguf ASP .Net 0 12-26-2008 09:29 AM
GIDS 2009 Java:: Save Big, Win Big, Learn Big: Act Before Dec 29 2008 Shaguf Python 0 12-24-2008 07:35 AM
Hungarian Notation Vs. Pascal Notation? Grey Squirrel ASP .Net 6 03-21-2007 09:42 AM
Dot notation V Bracket notation Robert Mark Bram Javascript 3 07-05-2003 03:59 AM



Advertisments