ravdeep
10-09-2007, 04:32 AM
hey guys i need URGENT help.. i gt some problem in solving some questions related to AOA.. help me find out solutions to these problems.. its urgent..!!
The ques are :-
2. Consider a function that reads a matrix of numbers and outputs the sum of all the entries. What do you think could be the worst-case complexity (running time) of this program?
3. Make guesstimates of average-case complexity when the matrix represents the consumption of various vegetables for each month of the year.
4. For the case when the matrix represents the number of days of the year for which an Infoscion reports to another Infoscion directly. Did you need to
make any assumptions about internal data structures?
5. Which of the following statements is/are true?
a. A square matrix algorithm that is O(n2), where n is the “height” of the matrix is O(m) where m is the total number of elements in the matrix
b. An O(n2) algorithm is an O(n3) algorithm is an O(n4) algorithm
c. An O(1034n) algorithm is an O(n) algorithm
d. An O(log2n) algorithm is an O(logen) algorithm is an O(log10n)
algorithm
e. Beyond a threshold problem size, an O(n2) algorithm always performs
better than an O(n3) one
f. Beyond a threshold problem size, an O(nk) algorithm always performs
better than an O(2n) one
g. Beyond a threshold problem size, an O(n2) algorithm always performs
better than an O(n3) one
h. Beyond a threshold problem size, an O(n2) algorithm always performs
better than an O(n3) one
post the answers on the forum.. thanks..!!
The ques are :-
2. Consider a function that reads a matrix of numbers and outputs the sum of all the entries. What do you think could be the worst-case complexity (running time) of this program?
3. Make guesstimates of average-case complexity when the matrix represents the consumption of various vegetables for each month of the year.
4. For the case when the matrix represents the number of days of the year for which an Infoscion reports to another Infoscion directly. Did you need to
make any assumptions about internal data structures?
5. Which of the following statements is/are true?
a. A square matrix algorithm that is O(n2), where n is the “height” of the matrix is O(m) where m is the total number of elements in the matrix
b. An O(n2) algorithm is an O(n3) algorithm is an O(n4) algorithm
c. An O(1034n) algorithm is an O(n) algorithm
d. An O(log2n) algorithm is an O(logen) algorithm is an O(log10n)
algorithm
e. Beyond a threshold problem size, an O(n2) algorithm always performs
better than an O(n3) one
f. Beyond a threshold problem size, an O(nk) algorithm always performs
better than an O(2n) one
g. Beyond a threshold problem size, an O(n2) algorithm always performs
better than an O(n3) one
h. Beyond a threshold problem size, an O(n2) algorithm always performs
better than an O(n3) one
post the answers on the forum.. thanks..!!