• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Tim Cooke
  • Paul Clapham
  • Jeanne Boyarsky
Sheriffs:
  • Ron McLeod
  • Frank Carver
  • Junilu Lacar
Saloon Keepers:
  • Stephan van Hulst
  • Tim Moores
  • Tim Holloway
  • Al Hobbs
  • Carey Brown
Bartenders:
  • Piet Souris
  • Frits Walraven
  • fred rosenberger

Time Complexity of a Collection

 
Ranch Hand
Posts: 133
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi,

Can some tell what is this time complexity of a collection??.
what its value of Arraylist, Vector, LinkedList.


regs

Vivek Nidhi
 
Rancher
Posts: 43028
76
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Complexity does not depend on the class, it depends on the operation, i.e. insert, lookup, delete. The javadocs for these classes give some clues of what can be expected.
 
Ranch Hand
Posts: 308
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator


Can some tell what is this time complexity of a collection?.
what its value of Arraylist, Vector, LinkedList.


Time Complexity is not something remaining constant throughout the universe. It varies with how (insert, lookup, iterate, clear etc) you use the collecton, what (application specific: to store shared or non shared resources, thread safe or non thread safe resources) you use the collection for and where(Implementation specific : batch, online, long continous use) you use it.

From http://en.wikipedia.org/wiki/Computational_complexity_theory


The time complexity of a problem is the number of steps that it takes to solve an instance of the problem as a function of the size of the input (usually measured in bits), using the most efficient algorithm. To understand this intuitively, consider the example of an instance that is n bits long that can be solved in n� steps. In this example we say the problem has a time complexity of n�. Of course, the exact number of steps will depend on exactly what machine or language is being used. To avoid that problem, we generally use Big O notation. If a problem has time complexity O(n�) on one typical computer, then it will also have complexity O(n�) on most other computers, so this notation allows us to generalize away from the details of a particular computer.


[ December 06, 2005: Message edited by: jiju ka ]
 
author
Posts: 4323
39
jQuery Eclipse IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Going back to the original question, Vector is theoretically slower than ArrayList or LinkedList, since its synchronized, but I don't have metrics for this. Are you concerned with which is faster or worst case algorithm analysis?
[ December 06, 2005: Message edited by: Scott Selikoff ]
 
Vivek Nidhi
Ranch Hand
Posts: 133
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thank you very much every one.
I just want to the stuff that's it, nothing much in detail

regs
Vivek Nidhi
 
This guy is skipping without a rope. At least, that's what this tiny ad said:
Garden Master Course kickstarter
https://coderanch.com/t/754577/Garden-Master-kickstarter
reply
    Bookmark Topic Watch Topic
  • New Topic