Katkat
Back

Analyze time complexity and threading trade-offs

ImcSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

This question evaluates understanding of worst-case time complexity for common data structure operations and the performance trade-offs between multithreading and single-threading, testing knowledge in the Software Engineering Fundamentals domain.

Answer the following conceptual questions.

1) Worst-case time complexity

State the worst-case time complexity (Big-O) for each operation and briefly justify.

  1. Remove an element (by value) from a sorted array.
  2. Check whether a given key exists in a hash table.
  3. Remove the minimum element from a min-heap.
  4. Find the i-th element in a sorted array (assume 0-based index) and return its value.

2) Multithreading vs single-threading

Is multithreading always faster than single-threading? Explain why or why not, and give at least one concrete example where multithreading is slower.