Question

In: Computer Science

Which of these statements are true and which are false? (a) If f(n) = Θ(g(n)) and...

Which of these statements are true and which are false?

(a) If f(n) = Θ(g(n)) and g(n) = Θ(h(n)), then h(n) = Θ(f(n))  

(b) If f(n) = O(g(n)) and g(n) = O(h(n)), then h(n) = Ω(f(n))

(c) If f(n) = O(g(n)) and g(n) = O(f(n)) then f(n) = g(n)                                                     

(d) 100n = Ω(n2)    

(e) In the merge-sort execution tree, roughly the same amount of work is done at each level of the tree.  

(f) An algorithm is randomized if its behavior is determined in part by values produced by a random-number generator.   

(g) Quicksort can be used as the auxiliary sorting routine in radix sort, because it operates in place.   

Solutions

Expert Solution


Related Solutions

Which of the following statements are true (T) and which are false (F)? a. In the...
Which of the following statements are true (T) and which are false (F)? a. In the Fisher’s exact test we test the following hypotheses: H0: the proportions of type A and type B discordant pairs are the same (pA=pB). H1: the proportions of type A and type B discordant pairs are not the same (pA≠pB). b. Using the McNemar’s test to analyze matched-pair data (paired samples) is a correct decision. c. The Fisher’s exact test is based on a 2x2...
Prove why f(n)=big omega(g(n)) then f(n)=o(g(n)) is NEVER TRUE. Prove why f(n) +g(n) =Theta(max(f(n),g(n)) is ALWAYS...
Prove why f(n)=big omega(g(n)) then f(n)=o(g(n)) is NEVER TRUE. Prove why f(n) +g(n) =Theta(max(f(n),g(n)) is ALWAYS TRUE
Indicate whether the following statements are true or false. (Select T-True, F-False. If the first is...
Indicate whether the following statements are true or false. (Select T-True, F-False. If the first is T and the rest F, enter TFFFFF). A) A white dwarf is the remnant of the star's core visible after the outer layers have been ejected. B) A planetary nebula is made of hot gas that shows emission line spectra. C) A planetary nebula forms when a star violently explodes. D) White dwarfs are small dense objects about the size of the Earth. E)...
Indicate whether the following statements are always true or can be false. (Select T-True, F-False. If...
Indicate whether the following statements are always true or can be false. (Select T-True, F-False. If the first is F and the rest T, enter FTTTTT). A) In order not to slow down, a bicycle moving at a constant velocity needs a small net force applied. B) If two objects have the same acceleration, they are under the influence of equal forces. C) If a net force acts on an object, the object's velocity will change. D) During the collision...
Decide which of the following statements are true and which are false. True False  Real gas molecules...
Decide which of the following statements are true and which are false. True False  Real gas molecules behave most ideally at low temperature and high pressure. True False  At constant temperature, the lighter the gas molecules, the smaller the average kinetic energy. True False  At constant temperature, the lighter the gas molecules, the smaller the average velocity. True False  In order for two separate 1.0 L samples of O2(g) and H2(g) to have the same average velocity, the O2(g) sample must be at a...
Which of the following statements are true and which are false? a) The magnitude of the...
Which of the following statements are true and which are false? a) The magnitude of the intercept, a, quantifies the steepness of the regression line b) We can apply one-way ANOVA to compare two independent samples. c) In one-way ANOVA we test the following hypotheses: H0: just one group-specific mean is different form the rest H1: all group-specific means are different d)One-way ANOVA cannot be applied if we have a paired-sample design.
Classify the following statements as true (T), or false (F). If you classify statement as false,...
Classify the following statements as true (T), or false (F). If you classify statement as false, correct it, or explain why it is false.             (a) If given stereoisomer rotates the plane of polarized light clockwise, its enantiomer rotates counter‐clockwise by exactly the same magnitude (b) If compound has one stereogenic center with S configuration, it always rotates the plane of polarized light counter-clockwise. (c) Molecule possessing stereogenic centers is always chiral. (d) Mixture of equal amounts of both enantiomers...
Which of the following statements are TRUE or False. (Explain why it’s true or false?) Subtracting...
Which of the following statements are TRUE or False. (Explain why it’s true or false?) Subtracting a positive number from a negative number always gives you a negative number. Subtracting two negative numbers always gives you a negative number. Subtracting a - b is the same as adding a + (-b). A positive number minus a negative number is always a positive number. The difference of a number and its opposite gives you zero. Zero minus a number is the...
Fill in the blanks with True (T) or False (F) for each of the given statements....
Fill in the blanks with True (T) or False (F) for each of the given statements. It is possible to directly form an acyl anion with an aldehyde and base. Electrophilic aromatic substitution is always faster with a heterocycle than with benzene. Pyridines are electron poor aromatic rings and are particularly good at nucleophilic aromatic substitution. Heterocyclopentadiene undergo electrophilic aromatic substitution primarily at the C-3 position. 1,3-diester is less acidic than a 1,3-ketoester, which is less acidic than an 1,3-diketone...
If f(n) = 3n+2 and g(n) = n, then Prove that f(n) = O (g(n))
If f(n) = 3n+2 and g(n) = n, then Prove that f(n) = O (g(n))
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT