You are given an n×n matrix of integers and asked to perform the following operation on it: 1.
Texas Instruments technical mcq question, verified with a worked answer. Free to practise - no sign-up.
You are given an n×n matrix of integers and asked to perform the following operation on it:
- Compute the minimum value in each row.
- Find the maximum of all the minimum values.
What is the time complexity of performing this operation?
Show answer & explanation
Finding the minimum in each of the n rows requires n comparisons per row, totaling n * n = n^2 operations. Finding the maximum of n values takes n-1 operations, giving overall O(n^2) time.
Step-by-step Derivation:
Step 1: An n x n matrix contains n rows of n elements each.
Step 2: Finding minimum of each row takes O(n) time, so for n rows it takes n * O(n) = O(n^2) time.
Step 3: Finding maximum of the n computed minimums takes O(n) comparisons.
Step 4: Total time complexity = O(n^2) + O(n) = O(n^2).