Big-O
Greg
Exactly what do we need to know about big-O notation?
Would a good question be finding the big-O of a method that sorts data
in a particular fashion that we haven't seen before based on its code?
Greg
This is a hard one to answer -- it is a bit broad. Everything?
First, the questions on the exam are about more than the "notation".
You should certainly understand the notation. What does it mean for an
algorithm to be O(n)? Or, O(n^2)? Etc, Etc, Etc.
But, you should also have good intuition about the behavior of the
types of algorithms we've seen. Given an understanding of an
algorithm's behavior, you should be able to characterize this behavior
in Big-O notation -- even if you haven't seen the particular algorithm
before.
You should be able to do this whether the algorithm is described in
words, or if it is given to you in code -- even for recursive code.
It is also important to remember that Big-O is any upper-bound, not
necessarily the tightest upper-bound.
> Would a good question be finding the big-O of a method that sorts data
> in a particular fashion that we haven't seen before based on its code?
This type of question is certainly possible. It is asking you to
analyze something you haven't seen before. It is in the same domain as
things you've seen before.
But, keep in mind, we can ask questions about familiar domains, such
as sorting, unfamilar domains that are readily and quickly understood
-- and about chunks of code that serve no particular purpose.
dc
"It is also important to remember that Big-O is any upper-bound, not
necessarily the tightest upper-bound. "
So if the question asks "What is the Big-O of blah" then how should we
interpret that? Do we give ANY Big-O or do we give the tightest
upperbound?
Greg
> interpret that? Do we give ANY Big-O or do we give the tightest
> upperbound?
If the question were phrased that way, you are most welcome to use
anything that is, in fact, an upper bound -- including O(N!).
But, we won't phrase a question like that. We'll tighten up the
language so that it gets the answer we want.
But, what is clear is this. Let's assume that foo() = O(1).
foo( 0might be inserting into an array, finding something in an array,
inserting at the head of a linked list. I don't care.
If we ask you, 'Is foo() O(N^3) ?" The answer is yes. If a constant is
an upper bound, a polynomial is sure an upper bound.
I hoep this helps.
tennis_pro
"average" case just the worst case? And do we have to know about space
complexity, which I don't really know what it is. Space complexity
doesn't depend on how many for loops you use or the number of steps
you take but how much space is required? Like putting stuff in a 2
dimensional array would have space complexity of O(n^2) but putting
stuff in an array and a linked list would have a space complexity of
O(2n)?
Greg
> "average" case just the worst case?
No! I definitely don't want to imply that at all. You certainly should
completely understand the behavior of an algorithm: best, worst,
expected, and all.
...we just haven't covered a formal notation other than Big-O. So, if
we would ask other things, we would have to use more words to aks the
question and more words to get the answer. But, we certainly WILL do
this.
> And do we have to know about space
> complexity, which I don't really know what it is. Space complexity
> doesn't depend on how many for loops you use or the number of steps
> you take but how much space is required? Like putting stuff in a 2
> dimensional array would have space complexity of O(n^2) but putting
> stuff in an array and a linked list would have a space complexity of
> O(2n)?
We haven't talked a whole lot about space complexity, per se. But, we
have talked about it in less formal ways. Consider the space trade-
offs we discussed between ArrayLists and LinkedLists or the
AdjacencyList and AdjacencyMatrix.
...you should have good intuition about this, should we ask.
>
> On Apr 29, 2:42 am, Greg <gkes...@gmail.com> wrote:
>
>
>
> > > So if the question asks "What is the Big-O of blah" then how should we
> > > interpret that? Do we give ANY Big-O or do we give the tightest
> > > upperbound?
>
> > If the question were phrased that way, you are most welcome to use
> > anything that is, in fact, an upper bound -- including O(N!).
>
> > But, we won't phrase a question like that. We'll tighten up the
> > language so that it gets the answer we want.
>
> > But, what is clear is this. Let's assume that foo() = O(1).
> > foo( 0might be inserting into an array, finding something in an array,
> > inserting at the head of a linked list. I don't care.
>
> > If we ask you, 'Is foo() O(N^3) ?" The answer is yes. If a constant is
> > an upper bound, a polynomial is sure an upper bound.
>
> > I hoep this helps.- Hide quoted text -
>
> - Show quoted text -