Time and Space Complexities
What is the time complexity of searching in an unsorted array?
O(n)
This sorting algorithm repeatedly compares adjacent elements and swaps them if they are in the wrong order.
Bubble Sort
This type of data structure has a root node and is made up of parent-child relationships with no cycles.
Tree
In a singly linked list, this is the term for the first node in the list.
Head
This type of search checks each element in an array one by one to find a target value.
Linear Search
Which of the following sorting algorithms has the best average time complexity?
- Merge Sort
- Bubble Sort
- Insertion Sort
- Selection Sort
Merge Sort
This searching algorithm works only on sorted arrays and repeatedly divides the search space in half.
Binary Search
This traversal method visits nodes in the order: left child, root, right child.
Inorder Traversal
In a doubly linked list, each node contains a reference to the next node and what additional reference?
A pointer to the previous node
This common string operation combines two strings into one.
Concatenation
What is the time complexity of inserting an element at the beginning of a linked list?
O(1)
This sorting algorithm divides the array into two halves, sorts each half, and then merges them together.
Merge Sort
In this type of graph, edges have a direction, meaning they go from one node to another in a specific way.
Directed Graph
In a linked list, this is the special value that indicates the end of the list when there are no more nodes.
Null (or None)
In many languages, strings cannot be changed after creation. What is this property called?
Immutability
You are given a function that iterates through an array of size n. Inside the loop, it performs a binary search on the same array. What is the overall time complexity of this function?
O(n log n)
This algorithm explores a graph by visiting all neighbors of a node before moving on to the next level.
BFS
This traversal uses a stack in its iterative implementation, exploring a branch until its end.
DFS
This type of linked list connects the last node back to the first node.
Circular Linked List
When inserting an element into the middle of an array, elements to the right must be shifted. This results in what time complexity?
O(n)
You are given a function that iterates through an array of size n. Inside the loop, it scans the entire array again to check for a condition. What is the overall time complexity?
O(n^2)
What are the two most efficient algorithms to find minimum spanning trees?
What is the Binary Search Tree property?
In a binary search tree, this property ensures that for every node, all values in the left subtree are smaller and all values in the right subtree are larger.
Compared to arrays, linked lists make which operation easier because no shifting of elements is required?
Insertion
Given the following array in python: arr = [0, 5, 4, 6], what is the result of arr[-2]
4