Win a copy of Mesos in Action this week in the Cloud/Virtualizaton forum!

# linked-based and time complexity question

Ryan Streetmen
Greenhorn
Posts: 4
Hello,

I have 2 questions and i cant figure them out

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
Posts: 48968
60
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
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.

Ryan Streetmen
Greenhorn
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
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
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
Posts: 48968
60
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
Posts: 4
ha thanks for the links yes thanks very much

Campbell Ritchie
Sheriff
Posts: 48968
60
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.