.png){kind=logo}
- | Page
CS 6515 EXAM 1
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 1 / 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)
- / 2
.png)