File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Beginning Java and the fly likes linked-based and time complexity question Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "linked-based and time complexity question " Watch "linked-based and time complexity question " New topic
Author

linked-based and time complexity question

Ryan Streetmen
Greenhorn

Joined: Apr 18, 2009
Posts: 4
Hello,

I have 2 questions and i cant figure them out

1 Advantage of a linked-based implementation over array based
is it
a the structure grows and shrinks in the linked based implementation
b the underlying structure is fixed size linked- based implementation
c elements can be accessed directly in linked-based implementation
d all of the above
e neither a b or c

Which algorthim has time complexity of O(log2 n)
a insertion sort
b selection sort
c bubble sort
d linear search
e binary search

I found the ans to question 2 but i am not sure i think it is binary search. On the first one i don't know links to websites can help too
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38851
    
  23
Welcome to JavaRanch and thank you for sorting out what Henry told you about.
We like people to demonstrate they have put lots of effort into their questions. Please, therefore, tell us what you think the correct answers are.
The correct answer to 2 is that none of them runs in O(nlog^2 n) time, but one algorithm runs in O(nlogn) time.
Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 4181
    
  21

The correct answer to 2 is that none of them runs in O(nlog^2 n) time, but one algorithm runs in O(nlogn) time.


Perhaps it was a formatting error. I think the question was asking for an algorithm that runs in log base 2, not log base 10 squared. There is one algorithm there that does run in log base 2 of n.


Steve
Ryan Streetmen
Greenhorn

Joined: Apr 18, 2009
Posts: 4
Campbell Ritchie wrote:Welcome to JavaRanch and thank you for sorting out what Henry told you about.
We like people to demonstrate they have put lots of effort into their questions. Please, therefore, tell us what you think the correct answers are.
The correct answer to 2 is that none of them runs in O(nlog^2 n) time, but one algorithm runs in O(nlogn) time.


the first one i think is the ans is C but the second one i think it is D no looked it up and i was binary sort worst case i think i am not really sure i am still searching .
Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 4181
    
  21

Ryan Streetmen wrote:the first one i think is the ans is C but the second one i think it is D no looked it up and i was binary sort worst case i think i am not really sure i am still searching .


How does the 'linked-list' work? How does an 'array-based' list work? Answer C was that there is direct access to an element. Knowing you have a list of links, how would you get to the 6th element? On the other hand, if you had an array, then how would you get the 6th element?
Ryan Streetmen
Greenhorn

Joined: Apr 18, 2009
Posts: 4
How does the 'linked-list' work? How does an 'array-based' list work? Answer C was that there is direct access to an element. Knowing you have a list of links, how would you get to the 6th element? On the other hand, if you had an array, then how would you get the 6th element?

linked - list is stucture one object refers to the next and array is it is in specific postion and array has fixed size but linked it does not have a fixed size it can grow or shrink
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38851
    
  23
Oh, it means log base; I thought it meant log squared. Sorry.

I think you are mistaken about q1, but I think binary search is correct for q2; it runs in logarithmic time. Do some Googling for search algorithms, and you find all sorts of things. A few I think actually useful follow: 1 2 and you can probably find other algorithms and structures on the same university website, maybe even one about links. I think those two links will answer all your questions for q2.
Ryan Streetmen
Greenhorn

Joined: Apr 18, 2009
Posts: 4
ha thanks for the links yes thanks very much
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38851
    
  23
You're welcome There are even better links about sorting algorithms; there is even one with little applets so you can watch the sorting before your very eyes, but I didn't find that one this time. You can search for Wirth Algorithms and there is a book by N Wirth about algorithms which you can download a pdf of.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: linked-based and time complexity question