1 | Page
CS 6515 EXAM 1 2025 UPDATED ACTUAL
EXAM WITH CORRECT SOLUTIONS.
Binary Search Runtime - correct answer- O(log n)
Merge Sort Runtime - correct answer- O(n log n)
Naive Multiplication of n-bit Integers Runtime - correct answer-
O(n²)
Fast Multiplication of n-bit Integers (Using Divide and Conquer)
Runtime - correct answer- O(n^log₂3) ≈ O(n¹.⁵⁹)
Median Finding Algorithm Runtime - correct answer- O(n)
FFT (Fast Fourier Transform) Runtime - correct answer- O(n
log n)
Gauss's Method for Multiplying Complex Numbers (Number of
Multiplications) - correct answer- 3 multiplications
, 2 | Page
Euclid's GCD Algorithm Runtime - correct answer- O(log(min(a,
b)))
Strassen's Algorithm for Matrix Multiplication Runtime - correct
answer- O(n^log₂7) ≈ O(n².⁸ⁱ)
Recurrence for Naive Multiplication of n-bit Integers - correct
answer- T(n) = 4T(n/2) + O(n)
Recurrence for Fast Multiplication (Divide and Conquer) -
correct answer- T(n) = 3T(n/2) + O(n)
Gauss's Formula for Multiplying Two Complex Numbers -
correct answer- (a+bi)×(c+di)=(ac−bd)+(ad+bc)i
Recurrence for Merge Sort - correct answer- 2T(n/2) + O(n)
Master Theorem Formula - correct answer- T(n) = aT(n/b) +
O(n^d)
CS 6515 EXAM 1 2025 UPDATED ACTUAL
EXAM WITH CORRECT SOLUTIONS.
Binary Search Runtime - correct answer- O(log n)
Merge Sort Runtime - correct answer- O(n log n)
Naive Multiplication of n-bit Integers Runtime - correct answer-
O(n²)
Fast Multiplication of n-bit Integers (Using Divide and Conquer)
Runtime - correct answer- O(n^log₂3) ≈ O(n¹.⁵⁹)
Median Finding Algorithm Runtime - correct answer- O(n)
FFT (Fast Fourier Transform) Runtime - correct answer- O(n
log n)
Gauss's Method for Multiplying Complex Numbers (Number of
Multiplications) - correct answer- 3 multiplications
, 2 | Page
Euclid's GCD Algorithm Runtime - correct answer- O(log(min(a,
b)))
Strassen's Algorithm for Matrix Multiplication Runtime - correct
answer- O(n^log₂7) ≈ O(n².⁸ⁱ)
Recurrence for Naive Multiplication of n-bit Integers - correct
answer- T(n) = 4T(n/2) + O(n)
Recurrence for Fast Multiplication (Divide and Conquer) -
correct answer- T(n) = 3T(n/2) + O(n)
Gauss's Formula for Multiplying Two Complex Numbers -
correct answer- (a+bi)×(c+di)=(ac−bd)+(ad+bc)i
Recurrence for Merge Sort - correct answer- 2T(n/2) + O(n)
Master Theorem Formula - correct answer- T(n) = aT(n/b) +
O(n^d)
