• 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
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

linked-based and time complexity question

 
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
 
Marshal
Posts: 79178
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Bartender
Posts: 4179
22
IntelliJ IDE Python Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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: 4179
22
IntelliJ IDE Python Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Marshal
Posts: 79178
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
ha thanks for the links yes thanks very much
 
Campbell Ritchie
Marshal
Posts: 79178
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
reply
    Bookmark Topic Watch Topic
  • New Topic