Exam prep Flashcards
(40 cards)
What is an algorithm?
An algorithm is a detailed, step-by-step method for solving a problem using a computer. It transforms an idea into a structured solution.
ALTERNATIVE
A detailed idea for how a problem can be solved using a computer program.
What is a data structure?
A data structure is an abstract way to organize data to enable efficient operations. It’s a core tool for writing fast programs and can often exist only in the programmer’s mind.
What is the purpose of time complexity?
Time complexity measures how long an algorithm takes to run based on the input size N. It focuses on complexity classes using asymptotic notation that ignore constant factors and lower-order terms.
What is the 3-SUM problem?
Given N unique integers, how many combinations of three numbers add up to zero.
What is tilde notation?
Asymptotic approximation, used informally to describe rough behavior for large inputs.
‘For large N, this behaves like…’
What is theta notation?
Tight bounds. Describes the actual/typical growth.
‘It’s exactly this, more or less, every time.’
What is big O notation?
Big O notation represents an upper bound. It describes the worst-case time complexity.
‘It won’t be slower than this.’
What is a heap?
A heap is a complete binary tree where in a min-heap, every parent is less than or equal to its children, and in a max-heap, every parent is greater than or equal to its children.
What is the time complexity for sorting an array into a binary heap?
Building a binary heap from an unsorted array takes O(n) time, where n is the number of elements. This is due to the ‘heapify’ process, which is more efficient than repeatedly inserting elements one by one (which would be O(n log n)).
What is the time complexity of:
for (int i = 0; i < N; i++) {
System.out.println(i);
}
This loop runs O(N) times because it iterates exactly N times, printing each value of i once.
What is the time complexity of:
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
System.out.println(i + “ “ + j);
}
}
This nested loop runs in O(N²) time because the inner loop executes N times for each of the N iterations of the outer loop, resulting in N × N = N² total operations.
What is the time complexity of:
for (int i = 0; i < N; i++) {
for (int j = 0; j < i; j++) {
System.out.println(i + “ “ + j);
}
}
This nested loop runs in O(N²) time because it forms a triangular number pattern that grows quadratically (specifically N(N-1)/2 operations).
Time complexity:
for (int i = 1; i < N; i = i * 2) {
System.out.println(i);
}
This loop runs in O(log N) time because the counter grows exponentially (doubling each time), resulting in approximately log₂N iterations.
Time complexity:
for (int i = N; i > 0; i = i / 2) {
for (int j = 0; j < i; j++) {
System.out.println(i + “ “ + j);
}
}
This nested loop runs in O(N) time because the total operations form a geometric series that sums to approximately 2N.
Time complexity:
for (int i = 0; i < N; i++) {
for (int j = 1; j < 1000; j = j * 2) {
System.out.println(i + “ “ + j);
}
}
The time complexity is O(N) because the outer loop runs N times while the inner loop always runs log₂1000 ≈ 10 times (constant).
Time Complexity:
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
for (int k = 0; k < N; k++) {
System.out.println(i + j + k);
}
}
}
This runs in O(N³) time because all three loops are linearly tied to N, multiplying their iterations: N × N × N = N³.
Time complexity:
for (int i = N; i > 0; i = i / 2) {
System.out.println(i);
}
This loop runs in O(log N) time because the counter decreases exponentially (by dividing by 2 each time).
What is the theta complexity of ‘for i = 0 to N’?
theta N
What is the theta complexity for ‘for i = 0 to N, for j = 0 to N’?
theta N²
What is the theta complexity for ‘for i = 0 to N, for j = 0 to i’?
theta N²
What is the theta complexity for ‘for i = N; i < 0, i /= 2’?
theta log N
What is the theta complexity for ‘for 0 to N³’?
theta N³
What is the theta complexity for a logarithmic loop nested in linear?
theta N log N
What are the two key properties of a heap?
Heaps must be complete binary trees with no gaps filled left-to-right, and satisfy either the min-heap or max-heap property.
