Data Structures and Algorithms
A linked-list implementation of a stack guarantees constant time performance but requires more space than an array implementation. - Answer- TRUE
Both implementations of pop and push guarantee constant time performance. Linked lists require additional memory (spac...
Data Structures and Algorithms
A linked-list implementation of a stack guarantees constant time performance but
requires more space than an array implementation. - Answer- TRUE
Both implementations of pop and push guarantee constant time performance. Linked
lists require additional memory (space) for storing a reference to the next node.
An algorithm that uses 12n2 + 4n log n operations is a ∼n2 algorithm. - Answer-
FALSE
It is a ∼ 12n2 algorithm.
Big-Oh notation is more precise than tilde notation at describing the growth of a
function. - Answer- FALSE
Big-Oh notation only provides an upper bound on the growth rate of a function. Tilde
approximation approaches the original function as N grows.
When implementing the Comparable interface, you should make sure that your
implementation of the compareTo() method specifies a total order over the objects. -
Answer- TRUE
When implementing the Comparable interface, you should make sure that your
implementation of the compareTo() method specifies a total order over the objects.
Mergesort - Answer- Stable and fast
Quicksort - Answer- Fast general-purpose sort
Shellsort - Answer- Not analyzed
Insertion sort - Answer- Works well with order
Selection sort - Answer- Optimal data movement
3-way quicksort - Answer- Works well with duplicates
Heapsort - Answer- Optimal time and space
Height of a binary heap with N keys. - Answer- log N
A binary heap is a complete tree. A complete tree is a tree with n levels, where for
each level d ≤ n − 1, the number of existing nodes at level d is equal to 2d. The
height of a binary heap is logN.
Height of a BST with N keys. - Answer- N
In the worst-case, the height of a BST is N, e.g., when keys are inserted in
increasing or de- creasing order.
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller Freshy. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $8.49. You're not tied to anything after your purchase.
