Complexity & Efficiency Awareness

Q1. What does Big-O describe?

1. A.The exact execution time needed
2. B.The minimum time for the task
3. C.The average case performance
4. D.Upper bound of the growth rate✓ Correct

Report an error in this question

Q2. What is O(1)?

1. A.Linear time growth
2. B.Constant time always✓ Correct
3. C.Quadratic time growth
4. D.Logarithmic time growth

Report an error in this question

Q3. What is O(n)?

1. A.Linear, proportional to input✓ Correct
2. B.Quadratic time growth
3. C.Constant time always
4. D.Exponential time growth

Report an error in this question

Q4. O(n) vs O(n^2) for large inputs?

1. A.They perform exactly equal
2. B.O(n^2) is faster overall
3. C.O(n) is faster overall✓ Correct
4. D.Cannot tell the difference

Report an error in this question

Q5. Space complexity measures?

1. A.Memory relative to input size✓ Correct
2. B.Disk storage used by files
3. C.Lines of code in the program
4. D.Screen pixels for the display

Report an error in this question

Q6. Array access by index?

1. A.O(1)✓ Correct
2. B.O(n^2)
3. C.O(n)
4. D.O(log n)

Report an error in this question

Q7. Single for loop through n?

1. A.O(1)
2. B.O(n)✓ Correct
3. C.O(log n)
4. D.O(n^2)

Report an error in this question

Q8. O(log n) typical of?

1. A.Binary search method✓ Correct
2. B.Bubble sort algorithm
3. C.Linear search scan
4. D.Array index access

Report an error in this question

Q9. Algorithm efficiency?

1. A.How readable the code looks
2. B.How fast you can type code
3. C.Time and space usage vs input✓ Correct
4. D.The number of lines of code

Report an error in this question

Q10. O(n) vs O(2^n)?

1. A.O(2^n) grows faster than O(n)✓ Correct
2. B.They grow at the same rate
3. C.It depends on the input data
4. D.O(n) grows faster than O(2^n)

Report an error in this question

Q11. Two nested n-loops?

1. A.O(n^2)✓ Correct
2. B.O(n)
3. C.O(2n)
4. D.O(n log n)

Report an error in this question

Q12. Merge sort space?

1. A.O(n)✓ Correct
2. B.O(1)
3. C.O(log n)
4. D.O(n^2)

Report an error in this question

Q13. Bubble sort best case?

1. A.O(n)✓ Correct
2. B.O(n^2)
3. C.O(1)
4. D.O(n log n)

Report an error in this question

Q14. Big-O vs Omega vs Theta?

1. A.O describes the lower bound only
2. B.Theta describes the upper bound
3. C.They are all the same thing
4. D.O: upper, Omega: lower, Theta: tight✓ Correct

Report an error in this question

Q15. Insert at array beginning?

1. A.O(n^2)
2. B.O(log n)
3. C.O(1)
4. D.O(n)✓ Correct

Report an error in this question

Q16. What is in-place?

1. A.A very slow sorting algorithm
2. B.O(1) or O(log n) extra space only✓ Correct
3. C.An algorithm that does not work
4. D.Uses lots of extra memory space

Report an error in this question

Q17. Hash table average lookup?

1. A.O(n)
2. B.O(log n)
3. C.O(1)✓ Correct
4. D.O(n^2)

Report an error in this question

Q18. Heap insert/extract?

1. A.O(1)
2. B.O(n log n)
3. C.O(log n)✓ Correct
4. D.O(n)

Report an error in this question

Q19. Why O(n log n) efficient for sorting?

1. A.It is slower than O(n^2) sorting
2. B.Theoretical lower bound for comparisons✓ Correct
3. C.It is the slowest sort possible
4. D.It only works on small inputs

Report an error in this question

Q20. Adjacency matrix space?

1. A.O(V^2)✓ Correct
2. B.O(V+E)
3. C.O(V)
4. D.O(E)

Report an error in this question

Q21. Naive Fibonacci complexity?

1. A.O(n)
2. B.O(n^2)
3. C.O(2^n)✓ Correct
4. D.O(n log n)

Report an error in this question

Q22. Splay tree amortized?

1. A.O(n)
2. B.O(n log n)
3. C.O(log n)✓ Correct
4. D.O(1)

Report an error in this question

Q23. Adjacency list vs matrix?

1. A.No meaningful difference exists
2. B.O(V+E) vs O(V^2), saves space sparse✓ Correct
3. C.Matrix is always better to use here
4. D.They use exactly the same space

Report an error in this question

Q24. Dijkstra with binary heap?

1. A.O(V^3)
2. B.O((V+E) log V)✓ Correct
3. C.O(V^2)
4. D.O(E)

Report an error in this question

Q25. P=NP asks?

1. A.Are primes equal to naturals
2. B.Verifiable in poly time means solvable?✓ Correct
3. C.Do programs always need parameters
4. D.Are pointers always needed in code

Report an error in this question

Q26. Naive matrix mult n*n?

1. A.O(n^2)
2. B.O(n^2 log n)
3. C.O(n^3)✓ Correct
4. D.O(n)

Report an error in this question

Q27. Strassen significance?

1. A.Same time as naive multiplication
2. B.It is slower than naive approach
3. C.Below O(n^3) at about O(n^2.807)✓ Correct
4. D.It only works on 2x2 matrices

Report an error in this question

Q28. What is NP-complete?

1. A.An easy problem with fast solution
2. B.In NP, all NP reduces to it in poly✓ Correct
3. C.A problem with known O(n) solution
4. D.A problem that is unsolvable always

Report an error in this question

Q29. Cache complexity?

1. A.Same as hash table complexity analysis
2. B.Cache misses affect real performance✓ Correct
3. C.Only measures the cache memory size
4. D.Same as space complexity of program

Report an error in this question

Q30. PSPACE?

1. A.Polynomial time class problems
2. B.Only applies to sorting algorithms
3. C.The simplest complexity class known
4. D.Polynomial space, contains P and NP✓ Correct

Report an error in this question