1

I have a midterm next week, and some of it has to do with code analysis/ sum simplification. I'm very lost, and am trying to understand this question my professor gave us on a practice work sheet.

Here is the pseudo code: 

 List <Integer> method( List <Integer> ints) { 
     for ( int i = 0; i < ints.size() / 2; i ++) { 
         swap(i, n − i − 1);
  }

The question is asking: Express the worst case running time of this method as a sum assuming that the List is an ArrayList? In which I got O(log n), since the size of the list is being divided in half every time.

But then the next question is: Express the worst case running time of this method as a sum assuming that the List is an LinkedList? Now I am confused, I know that ArrayLists and LinkedLists have different time complexities, but wouldn't the answer be the same O(log n)?

Also how would I express this as a sum for each question? This is not homework, but I am trying my best to understand this subject.

Improve this question
6
  • In the ArrayList scenario it's nlog(n). in the LinkedList Scenario its n^2.log(n) Commented Apr 14, 2016 at 1:38
  • @ImeshaSudasingha and this is because the run time of a list is O(n), and the run time of linked lists are O(n^2)? That makes a lot of sense. Commented Apr 14, 2016 at 1:42
  • @ImeshaSudasingha why would it be nlogn? If ints is an ArrayList, it would just be O(n). If it is a LinkedList, it would be O(n^2), because you have to traverse the list again for each element. There should not be any logs because the length only gets cut in half once - not every iteration. Commented Apr 14, 2016 at 1:48
  • Sorry, it should be O(n) and O(n^2). Commented Apr 14, 2016 at 1:51
  • @LukeLaFountaine Im confused, why wouldn't it get cut in half on every iteration since it is in a loop? Commented Apr 14, 2016 at 1:53

1 Answer 1

Reset to default
1

If ints is an ArrayList, it can access any element in constant time. So it is going through the first half of the elements and swapping them with the corresponding element from the second half. This is still considered to be O(n) because the total number of iterations will be 1/2 * (n), and you drop the constant for the big O notation.

If ints is a LinkedList, you do not have constant time access to any element- you have to traverse the entire list to get to each element. So for each element in the first half of the list, you are iterating through again to find the corresponding element from the second half. This leads to a worst case runtime of O(n^2).

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Thanks! This answered my question, if i was to put this in the form of a sum how would i go about it?
for the first one: Σ i from i=0 -> n
for the second: Σ i*n from i=0 -> n
sorry not sure how to do the correct sum notation in markdown

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.