i have this short homework assignment for my c++ class...i'm not asking anyone to do it for me, but just help me get started...i don't even know what they are looking for in this alright, its setup with directions at the top and then 4 boxes with seperate calls in each one directions: Given a list containing N data items, develop worst-case, order-of-magnitude estimates of the execution time of the following List ADT operations, assuming they are implemented using an array. Briefly explain your reasoning behind each estimate first box: insert O( ) explanation: second box: remove O( ) explanation: third box: gotoNext O( ) explanation: fourth box: gotoPrior O( ) explanation: any help is appreciated in getting me started or even explaining to me what i'm supposed to do...the directions just aren't clear to me

Look at the ADT, then think to yourself in terms of "N" how long would it take for this method to run? Suppose you have this chunk of code: for(int i=0;i>n;n++) blah; Assuming the "blah" runs in a fixed amount of time INDEPENDENT of N then the worse case: O() = N Example: Since you are using a List with an array, for removing an item out of the list, what would be the longest it would take given you remove from the front, middle or end. You are looking for the worst case which will take the longest in terms of N.

What it's looking for is the order of magnitude for the runtime of each of those functions when they're implemented using an array (presumably a standard C++ array, not a linked list or fancy vector class). I don't know how you've learned execution time magnitudes, but I learned them using big-O notation. So, if a function takes one step for each data member passed to it, it's said to have a magnitude of O(n). If it takes the same amount of time no matter how many members there are, it's O(1). If it's slower for lots of members, but not by much, it's O(log(n)) or O(nlog(n)), if it increases quickly as more members are added, it's O(n^2). I think there are more than that, but I don't remember them all (it's probably the thing I was worst at in the AP C++ curriculum and I haven't done it since May anyway ). Edit: Damn, you beat me to it

ok so with what you are saying, shouldn't all the 4 functions above just be O(n)? i mean an insert function should just insert a value into the array and that should just take one step...it's not telling me to move all the elements in the array or at least some of them and then pass in the insert function to the open space...or am i thinking of it wrong? i mean should i be thinking that with an insert function, i have to find the cursor, make the array bigger to fit the new value and then insert it? same with remove...with that would i have to find the cursor, tell the cursor to go to a specific value, remove that value, and then make the array smaller by 1? the gotoNext and gotoPrior both also seem like 1 step functions...am i missing something? i mean this is a "Laboratory 3: Postlab Exercise" but it doesn't say that i should be relating this to lab 3 in any way...it just says "given a list containing n data items" thanks in advance

It's asking you about the worst case scenario for those list operations. And, you must consider the complete operation, meaning moving the cursor/pointer to the desired element, inserting or removing, and then moving data elements to create or fill-in the gap.

ok for the insert: worst case you will have to find the cursor, make the array larger by 1, move all the elements of the array (upto where you want to insert) forwards by one, leaving room to insert, move teh cursor to that spot, and insert. O(1) is used if it takes the same amount of time per item no matter how many items we aretrying to insert remove: find the cursor, move it to the data item you want to reomve, remove that item, move all the items in the array up to that one down by 1 and make the array smaller by 1. same as above where it takes the same amount of time no matter how many items we are trying to remove gotoNext: this just advances teh cursor and the function takes one step for each data member passed to it gotoPrior: this just moves the cursor back which also only takes 1 step

The big-O notation is used to describe the relationship between the time it takes to perform an operation, and the size of the data set being operated on. For insert or remove, you're moving the cursor up to N times. You're also going to move up to N elements in the array. The total time it takes to perform an insert or remove is linearly related to the number of elements in the array, so it is O(n). Advancing or reversing a cursor one element is a constant time operation. The time it takes to move the cursor one element does not depend on how many elements are contained in the array, so it is O(1).