# linked-based and time complexity question

Ryan Streetmen

Greenhorn

Posts: 4

posted 7 years ago

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

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

Posts: 48968

60

posted 7 years ago

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(

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(

*n*log^2*n*) time, but one algorithm runs in O(*n*log*n*) time.
posted 7 years ago

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.

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

Posts: 4

posted 7 years ago

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 .

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^2n) 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 .

posted 7 years ago

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 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?

Steve

Ryan Streetmen

Greenhorn

Posts: 4

posted 7 years ago

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

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

posted 7 years ago

Oh, it means log base; I thought it meant log squared. Sorry.

I think you are mistaken about q1, but I think

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.
Campbell Ritchie

Sheriff

Posts: 48968

60

posted 7 years ago

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.