Review for Midterm 3: From Linked Lists To Trees

Flashcards created from the lecture notes for review and quiz preparation.

Performance of an Algorithm

The number of basic operations needed to solve a problem.

Big O notation

Indicates the growth rate of the number of operations with respect to increase of size of the problem (n).

O(1)

Constant time complexity.

O(log(n))

Logarithmic time complexity.

O(n)

Linear time complexity.

O(n log(n))

Log-linear time complexity.

O(n^2)

Polynomial time complexity with a quadratic growth rate.

O(2^n)

Exponential time complexity.

Abstract Data Type (ADT)

Describes a set of objects sharing the same properties and behaviors.

Singly Linked List

A data structure consisting of nodes where each node contains data and a reference to the next node.

Doubly Linked List

A linked list where each node contains a reference to both the next and the previous node.

Recursion

Occurs when a method calls itself directly or indirectly.

Sequential Search

Search algorithm that checks each element in sequence until the desired value is found.

Binary Search

Search algorithm that only makes sense when the container is sorted and repeatedly divides the search interval in half.

Hash Table

A data structure that stores associations (key-value pairs) by converting keys into integers via a hash function.

Collision in Hash Tables

Occurs when two keys hash to the same index; can be handled using methods like chaining.

Binary Search Tree (BST)

A binary tree in which for every node, the element is greater than or equal to all elements in the left subtree and less than or equal to all elements in the right subtree.