Confused on this one.... NO CODING JUST EXPLANATIONS 1) Finding an empty row in
ID: 3697156 • Letter: C
Question
Confused on this one....
NO CODING JUST EXPLANATIONS
1) Finding an empty row in a 2-D array where empty is defined as an element with a 0 entry.
For the problem segment above, do the following:
- Create an algorithm(PSEUDOCODE) to solve the problem
- Identify the factors that would influence the running time, and which can be known before the algorithm or code is executed. Assign names (such as n) to each factor.
- Identify the operations that must be counted. You need not count every statement separately. If a group of statements always executes together, treat the group as a single unit. If a method is called, and you do not know the running time of that method, count it as a single operation.
- Count the operations performed by the algorithm or code. Express the count as a function of the factors you identified in Step 2. If the count cannot be expressed as a simple function of those factors, define the bounds that can be placed on the count:the best case (lower bound) and worst case (upper bound).
- Determine what the Best Case Inputs are, and the Worst Case Inputs are, and the efficiency of your implementation
- Transform your count formula into big-O notation by:
- Taking the efficiency with worst case input
- Dropping insignificant terms.
- Dropping constant coefficients.
Explanation / Answer
Algorithm to find row with all zero entries
1) no of rows = m , no of columns = n
2) for i = 1 to m
for j = 1 to n
if a[ i, j] != 0 break; endif;
end for
if j == n+1 print i is the row with all zero entries
k=k+1
endif
end for
3. Output/print there are k rows with all zero entries
___
Time complexity is O(mn) = O(n2)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.