Scribd
Upload
2 views2 pages

Algorithm Assignment Solutions

The document contains solutions to algorithm assignment questions, providing Big-O notations and complexities for various algorithms. It includes comparisons of functions, sorting algorithms, and discusses concepts like best, worst, and average case scenarios. Additionally, it covers specific algorithmic strategies and their time complexities.

Uploaded by

aman.mirza.7vc
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
2 views2 pages

Algorithm Assignment Solutions

The document contains solutions to algorithm assignment questions, providing Big-O notations and complexities for various algorithms. It includes comparisons of functions, sorting algorithms, and discusses concepts like best, worst, and average case scenarios. Additionally, it covers specific algorithmic strategies and their time complexities.

Uploaded by

aman.mirza.7vc
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

ALGORITHM ASSIGNMENT SOLUTIONS

Q1: Big-O simplifies to O(n^4). Constants: c=21, n0=1.

Q2:

(a) O(n^2)

(b) O(2^n)

(c) O(n log n)

(d) O(n!)

Q3: All statements are TRUE.

Q4:

1. Θ(n^2)

2. Ω(n)

3. O(n!)

4. Θ(n log n)

5. Ω(log n)

Q5:

(a) n^3 > n^2 log n

(b) 3^n > 2^n

(c) √n > log n

(d) n! > 2^n

Q6:

log log n < log n < √n < n < n log n < n^2 < n^3 < 2^n < n! < 2^(2^n)

Q7:

Best: minimum time

Worst: maximum time

Average: expected time

Q8:

Transitivity: if f=O(g), g=O(h) then f=O(h)

Reflexive: f=O(f)

Q9: O(n^2)

Q10: O(n^3)

Q11: O(n^2)
Q12: Selection sort, O(n^2)

Q13: A=O(n^2), B=O(n^2), C=O(n log n)

Q14: Divide, Conquer, Combine

Q15:

(a) O(n log n)

(b) O(n^2 log n)

(c) O(n^2)

(d) O(log n)

(e) O(n log^2 n)

Q16: O(n log n), space O(n)

Q17: Rank=6, comparisons≈log n

Q18: O(log n)

Q19: O(2^n)

Q20: Brute force = simple but slow

Q21: Sorted → [11,12,22,25,64]

Q22: Sorted → [1,2,4,5,8]

Q23: O(n+k), space O(k)

Q24: O(d(n+k))

Q25: Lower bound Ω(n log n)

Q26: Max subarray → O(n log n)

Q27: Karatsuba → O(n^1.58)

Q28: Closest pair → (2,3) & (3,4)

Q29:

Merge vs Quick, Counting vs Radix, etc.

Q30:

Polynomial better than exponential

You might also like