ArrayList BinarySearch vs Contains

[Dave Sexton]

Hi Peter,

T = total time
A = (constant) Initialization
B = (constant) The time to test one element in a collection
N = (Variable) The number of elements in a collection

What information is missing?

I thought the example:

T = A + B*N + C*N*N

was representative of the behavior of any algorithm that exhibits an average
time of:

t = A/N + B + C*N

It seems to me that for any algorithm with an average time of t, governed by
this forumla, there must be some way to express that using the O notation;
However, O(A/N + B + C*N) just doesn't seem correct to me.

I don't understand why the average time may vary depending upon the algorithm
because as soon as another variable (or constant) is introduced into an
algorithm this formula would no longer apply.

Conceptually, it seems reasonable that t will be close to N^2, given an
infinite result set, but I lack in the math skills to prove it. I suspect
that "asymptotic" is the keyword here, again, but that's currently outside the
scope of my understanding. I should spend some time and RTFM

(Thanks for all the help everyone)

--
Dave Sexton

[...]
Here, O(N^2) notates the worst case?

Not necessarily. It only represents worst-case if you are specifically
looking at the algorithm's behavior in the worst-case. Here, O(N^2) could
very well be the average case. Bill's example didn't actually specify the
algorithm, so there's no way to know in this particular example. But when
calculating order for an actual algorithm, you would have that information
and would be able to say whether the calculated order represented a best,
average, or worst case scenario.

Pete

 

[Brian Gideon]

Hi Brian,

Actually, I thought more about what you said and it's clear to me now that you
meant O(1) doesn't reveal the actual time it takes, it just shows that the
time is constant, whatever value it may be.

10 still sounds arbitrary to me, however

It comes from the MSDN documentation. But, yeah, it's very arbitrary.
I think if you ran your own tests you'd observe a break even point that
was close to 10, but probably not exactly 10.

 

[Peter Duniho]

Hi Peter,

T = total time
A = (constant) Initialization
B = (constant) The time to test one element in a collection
N = (Variable) The number of elements in a collection

What information is missing?

I can't tell you unless you tell me what algorithm you're asking about.
Perhaps none. Perhaps all sorts of information. It depends.

I thought the example:

T = A + B*N + C*N*N

was representative of the behavior of any algorithm that exhibits an
average time of:

t = A/N + B + C*N

It is, by definition. The latter equation is simply the former, divided by
the number of elements. It's by definition the mathematical average of the
time for a given element.

It seems to me that for any algorithm with an average time of t, governed
by this forumla, there must be some way to express that using the O
notation; However, O(A/N + B + C*N) just doesn't seem correct to me.

Good...because it's not.

I don't understand why the average time may vary depending upon the
algorithm because as soon as another variable (or constant) is introduced
into an algorithm this formula would no longer apply.

The formula Bill gave is just an example. It applies only to a theoretical
example algorithm, and can't be used generally. He's just trying to show
how an algorithm with theoretically worse order can still be better for
small numbers of elements.

Pete

 

[Dave Sexton]

Hi Peter,

I understood what Bill was trying to show me - that part was clear.

My confusion was in the fact that I thought the formula WAS the algorithm
after I completed the article, but I think I got it now.

My own inattentive mistake. Thanks for clearing that up.