Bissoy.com
Doctors Medicines MCQs Q&A

Let W(n) and A(n) denote respectively, the worst case and average case running time of an algorithm executed on an input of size n. Which of the following is ALWAYS TRUE? 

Let W(n) and A(n) denote respectively, the worst case and average case running time of an algorithm executed on an input of size n. Which of the following is ALWAYS TRUE?  Correct Answer A(n) = O (W(n))

The correct answer is "option 3".

CONCEPT:

There are three types of complexities:

1. Worst case: It is the maximum running time taken by any algorithm. 

2. Average case: It is the average running time taken by any algorithm. 

3. Best case: It is the minimum running time taken by any algorithm. 

EXPLANATION:

The average case time can be equal to or lesser than the worst case.

So, A(n) would be the upper bound case by W(n).

Also, it will not be a strict upper bound as it can be the same as an average case like Merge sort.

Therefore,

A(n) = O(W(n))

Hence the correct answer is "option 3".

Related Questions

Two beams PQ (fixed at P and with a roller support at Q, as shown in Figure I, which allows vertical movement) and XZ (with a hinge at Y) are shown in the Figures I and II respectively. The spans of PQ and XZ are L and 2L respectively. Both the beams are under the action of uniformly distributed load (W) and have the same flexural stiffness, EI (where, E and I respectively denote modulus of elasticity and moment of inertia about axis of bending). Let the maximum deflection and maximum rotation be δmax1 and θmax1, respectively, in the case of beam PQ and the corresponding quantities for the beam XZ be δmax2 and θmax2, respectively. Which one of the following relationships is true?
A program consists of two modules executed sequentially. Let f1(t) and f2(t) respectively denote the probability density functions of time taken to execute the two modules. The probability density function of the overall time taken to execute the program is given by
Questions below followed by three quantities. Find the relationship between them. Quantity I: In a class with a certain number of students if a teacher weighing 78 kg is added, then average weight of class is increased by 2 kg. If one more teacher weighing 66 kg is added, then the average weight of the class increases by 3.5 kg over the original average. What is the original average weight (in kg) of the class? Quantity II: The average age of 16 students and their teacher's age is 16 years. If the teacher's age is excluded, the average reduces by 2. What is the teacher's age? Quantity III: Average weight of three friends A, B and C is 46 kg. Another person D joins the group and now the average is 45 kg. If another person E whose weight is 6 kg more than D, joins the group replacing A, then average weight of B, C, D and E becomes 47 kg. What is the weight of A (in kg)?
A queue is implemented using a non-circular singly linked list. The queue has a head pointer and a tail pointer, as shown in the figure. Let n denote the number of nodes in the queue. Let enqueue be implemented by inserting a new node at the head, and dequeue be implemented by deletion of a node from the tail. Which one of the following is the time complexity of the most time-efficient implementation of enqueue and dequeue, respectively, for this data structure?
Worst case is the worst case time complexity of Prim’s algorithm if adjacency matrix is used?
Read the passage carefully and select the best answer to each question out of the given four alternatives.
Public opinion may be passive and false or active and real. It is claimed in theory that all governments are ultimately based on the opinion or sanction of the governed. But we find that in practice the people's rights are often trodden down and tyranny and oppression are allowed to continue. The government does it not because the people want it to do so but because they are too idle, too uneducated and too disunited or timid to oppose the govern ment. Such public opinion is passive and false and not an active verdict. But when we find people alert, intelligent and determined to let the government know their will, when they want to exercise actively their voice in the management of their country, we have an instance of true or active public opinion. True public opinion is formed by and expressed through the press, the platform, political parties and educational institutions. These have sacred duties to perform, duties on which depends the ultimate good of the entire community. The press today wields a tremendous influence, So it should support the causes and move ments and condemn the wrong one's and thus teach people to form correct opinion. A free and fair press ventilates the grievances of the public. Thus a healthy relationship develops between the people and the government through out an unbiased press. Political parties also help to create and regulate opinions. No less important part is played by the educational Institutions which train the minds of the young people who will be the citizens of tomorrow. It has been said that modern Germany and China have been made by their universities. It is necessary that the young and the growing minds should imbibe the spirit of fellow-feeling, the spirit of tolerance, the habit of compromise, and show due regard for the feelings and opinion of others without which a democratic society cannot function, let alone succeed. When there is true awakening of the people, we shall have the real and conscious public opinion. And justice will reign on earth and truly will the voice of the people be the voice of God.
Which of the following is not the reason for the oppression caused to general public by the running government in the country?
Questions below followed by three quantities. Find the relationship between them. Quantity I: Average age of 14 members of team is 25 years. While oldest member of the team is 26 years older than youngest member of the team. Out of remaining 12 members of team, average age of six members of team is 28 years and the remaining six members is 20 years. What is the age of oldest member of the team? Quantity II: Average age of Nitu, Rekha and Shyam is 17 years. Two new persons Divya and Raju joined them so that average age of all become 19 years. If Divya is 2 years older than Raju and Rekha is 2 years older and 1 year older than Shyam and Nitu respectively. What is sum of the average age of Nitu and Shyam together and average age of Divya and Rekha together? Quantity III: The average age of father, mother and their two sons is 27.5. Five years ago, the ratio of ages of father, mother and two sons (elder and younger) is 7 : 5 : 2 : 1. Find the sum of ages of two sons after 7 years.
Which of the following statements are true with regards to the selection of a sample size? (i) The sample size (n) may be a fixed percentage of lot size (N). (ii) The sample size (n) may be kept constant irrespective of lot size (N). (iii) Sample size (n) can be selected at the personal whim of the inspector.
A word arrangement machine, When given an input line of words, rearranges it in every step following a certain rule. Following is an illustration of an input line of words and various steps of rearrangement.
Input: gone are take enough brought station
Step 1: take gone are enough brought station
Step 2: take are gone enough brought station
Step 3: take are station gone enough brought
Step 4: take are station brought gone enough
And Step 4 is the last step for this input. Now, find out an appropriate step in the following question following the above rule. Question:
Input: car on star quick demand fat
What will be the third step for this input ?
The average of eight batsmen J, K, L, M, N, O, R, and T is compared. The number of batsman having average less than L are same as the number of batsman having average more than M. Average of T is less than M and more than K. Average of L is less than K. Average of two batsman lies between the average of M and L. Average of O is less than N and K both. Which of the following can be the correct sequence of their averages?