On Thu, Nov 29, 2001 at 03:05:41PM -0500, Michael G Schwern wrote:
> On Thu, Nov 29, 2001 at 11:34:24AM -0800, Chris Thorpe wrote:
> >
> > On Thu, 29 Nov 2001, Yanick wrote:
> >
> > > On Thu, Nov 29, 2001 at 01:34:02PM -0500, Michael G Schwern wrote:
> > >
> > >>> Yesterday, I saw an interesting related exercise. Write a program that
> > >>> reads the lines from a file and outputs the middle line. The kicker is
> > >>> that you can't use arrays.
> > > >
> > > > I'll interpret that as O(1) memory, O(n) time.
> >
> > You can't do it in O(1) memory and O(n) time.
> <snip>
> > If you elect to use O(1) memory, then you have to use O(1.5*n) time,
> > as the already submitted examples do.
> >
> > It seems silly to try to use O(n/2) memory if you aren't allowed to use
> > an array.
>
> O(n) == O(1.5*n) == O(n/2).
>
>
> A Crash Course On BigO Notation As Presented By A Guy Who Failed
> Fundamental Data Structures And Algorithms 1 *
>
> O(1) means it runs in a fixed amount of time regardless of how much
> data is to be processed. A hash is an O(1) algorithm.
Eh, no. A hash gives you O(1) *expected* search/update time, if you've
found an appropriate hash function.
> O(logn) means as you increase the amount of data, the time required
> will increase logarithmicly. In order to double the run time
> you have to exponentially increase the data.
No, it doesn't mean the time increases logarithmically. It means the time
will increase *at most* logarithmically. A significant difference.
Here's a more precise definition:
f(n) = O(g(n)) if and only if there are N > 0 and c > 0, such
that for all n > N, |f(n)| < |c * g(n)|.
> BigO is an expression of how the algorithm will perform as the data
> size approaches infinity. It is also refered to as worst-case
> analysis. As such it's a tad conservative. There's also best-case
> analysis and average-case analysis, I forget the symbols... theta or
> something. A basic quicksort is O(n**2), but this only happens if you
> try to quicksort an already sorted array. It's average case is nlogn.
> Most practical quicksort implementations have safeguards to prevent
> their worst case.
Big-Oh gives upper bounds of functions, little-oh does also, but gives
stronger upper bounds. Big-Omega and little-omega give lower bounds
of functions. A function that's both Big-Oh and Big-Omega of another
function is said to be Big-Theta of said function. (A function cannot
be both little-oh and little-omega of another function - hence there's
no little-theta.) There's also Big-Lambda and little-lambda.
Abigail
