Please help me with these Data structure problems. I have a test coming up and I

Question

Please help me with these Data structure problems. I have a test coming up and I don't understand these type of problems. Big O notation is still unclear from me. I'll be quick for awarding points.

1.)

Suppose each row of an n X n array A consists of l's and O's such that, in any row i of A, all the l's come before any O's. Also suppose that the number of 1's in row i+1 is at least the number in row i+1,for i= 0,1,..., n- 2.

Assuming A is already in memory, describe a method running in O(n) time (not O(n2)) for counting the number of 1's in A.

2.)

Given an n-element unsorted array A of n integers and an integer k, de- scribe a recursive algorithm for rearranging the elements in A so that all elements less than or equal to k come before any elements larger than k. What is the running time of your algorithm?

Explanation / Answer

1)

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.