• Post Reply Bookmark Topic Watch Topic
  • New Topic

time complexity  RSS feed

 
Ranch Hand
Posts: 96
10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
for linkedlists :

how is the time complexity computed in the methods : 1. remove(int index) and  2. remove(Object ob)

will it be different ? May I know , if yes how, if not , how ? how exactly compute for the two ?
 
Saloon Keeper
Posts: 7994
143
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well, one iterates over the nodes until it hits the specified index, and the other iterates over the nodes until it hits the specified element. Regardless, they both have to iterate a chain of nodes once.
 
Lilou Laure
Ranch Hand
Posts: 96
10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
so the time complexity will be O(n) except when we refer to the first or last elements, for which it'll be O(1).

Similarly in doubly linked lists too, when either of the remove methods are used, it'll be the same as above right ? because even though finding the successor and predecessor will be O(1), to iterate to the desired element it may take O(n) . Is this right ?
 
Marshal
Posts: 56610
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Lilou Laure wrote:. . . when we refer to the first or last elements, for which it'll be O(1).
Don't try to reduce complexity to fit in such corner cases. Even in the case of extreme values, the complexity remains O(n), even though n = 1. That does not reduce to constant time.
Similarly in doubly linked lists too, when either of the remove methods are used, it'll be the same as above right . . . to iterate to the desired element it may take O(n) . Is this right?
Yes; the time taken on average to remove something from a linked list remains linear time; there is no such thing as O(n ÷ 2) complexity.
 
Lilou Laure
Ranch Hand
Posts: 96
10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
thanks a lot campbelle ritchie   
 
Lilou Laure
Ranch Hand
Posts: 96
10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
But the same remove (int index) for an arraylist will take O(1) i.e. constant time ? and the same goes for get(index) ? but remove (object) for an arraylist will take linear time O(n)?
 
Stephan van Hulst
Saloon Keeper
Posts: 7994
143
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Lilou Laure wrote:so the time complexity will be O(n) except when we refer to the first or last elements, for which it'll be O(1).

Complexity classes are not concerned with specific cases, they're only used to indicate how fast a function grows.

You can say "Getting an element at a fixed index in a linked list of size n performs in O(1)", or you can say "Getting an element at a given index om a linked list of size n performs in O(n)", but these are different operations. It doesn't matter what the exact value of n is. Here's an example of an O(1) operation:

Even though this method gets an element that's possibly in the middle of a linked list (if the list has close to a 100 elements), it still operates in O(1), because the amount of time it takes does not depend on the size of the list. It will take equally long for a list of a thousand elements.

Note that it's important to specify what n stands for. In your first method, n was taken to be the shortest distance between the index and the start or end of the list. In your second method, n was taken to be the size of the list. If instead, for the method remove(int index), d stands for the shortest distance between the start and end of the list, and n stands for the size of the list, then the operation performs in O(d), not O(n).
 
Campbell Ritchie
Marshal
Posts: 56610
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That is a good question; have a look at the documentation for it.
All of the other operations run in linear time (roughly speaking).
The first stage of removal runs in constant time because it is possible to find each element from its index with the underlying array; moving the remaining elements in the array to occupy that space however takes a time dependent on the size of the List.
 
Lilou Laure
Ranch Hand
Posts: 96
10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
OK fine !

Thanks campbelle ritchie and stephan van hulst  for your instant and helpful responses  
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!