Hi Everyone,
I'm doing a project at university that requires a complexity analysis (big-O style) of my program. I've used the Vector class considerably and I was wondering if anyone had an analysis for methods such as add(), get(), and indexOf().
Thanks,
Frank.
P.S. The project's due soon - so hurry!!!
> The add() is in O(n) on a vector whereas is in O(1) in
> a LinkedList
> The get() and indexOf() are in O(n) (linear time).
Are you sure about that?
Vector:
add: n
get:1
remove: n
indexOf :n
set: 1
LinkedList:
addEnd/addHead/getHead/getEnd: 1
add:n/2
remove(int index): n/2
remove(object index): n
get:n/2
indexOf :n
set: n/2
So if you're doing lots of gets/sets on random elements, use an ArrayList, if you're doing lots of adding and removing at the end / start of a list, use LinkedList.
> Vector:
> add: n
> get:1
> remove: n
> indexOf :n
> set: 1
>
> LinkedList:
> addEnd/addHead/getHead/getEnd: 1
> add:n/2
> remove(int index): n/2
> remove(object index): n
> get:n/2
> indexOf :n
> set: n/2
>
This is big O notation so you drop all coefficients for the big O. So your 1/2's should disappear.
Plus your "add" number was off... open up the src.jar and look at the vector class
Vector:
add: 1
get:1
remove: n
indexOf :n
set: 1
LinkedList:
addEnd/addHead/getHead/getEnd: 1
add:n
remove(int index): n
remove(object index): n
get:n
indexOf :n
set: n
Add is not off actually, since the WORST case add is when the ArrayList has to create a new arraylist of objects (double the size of the old), and copy all the old elements to the new array. Thus, you get order n time. The docs maybe wrong in that case.
But you're right about the co-efficients. I just like to put them in cause it's the worst case. When dealing with simple lists, I think you should think about the coefficient because it can make a difference in your program. I end up coding a lot of variable sized arrays myself sometimes when I think that the overhead of using a arraylist will be too much. Mostly only in graphics rendering code.
> Add is not off actually, since the WORST case add is
> when the ArrayList has to create a new arraylist of
> objects (double the size of the old), and copy all the
> old elements to the new array. Thus, you get order n
> time. The docs maybe wrong in that case.
yeah you are right I just looked at the function
ensureCapacityHelper()
in the add function in the class and it does try to recreate the Vector if necassary. I suppsose you could get around that by supplying a sufficiently large initial capacity for the vector.
> But you're right about the co-efficients. I just like
> to put them in cause it's the worst case. When dealing
> with simple lists, I think you should think about the
> coefficient because it can make a difference in your
> program.
I am a big runtime analisys fan and do pay attention to coefficients,. just not when I am looking at big O ;)
