Write whether the following statements are true or false. If true prove why it i

Question

Write whether the following statements are true or false. If true prove why it is true, if false prove why it is false.

a.) all square numbers can be written as the sum of two primes.

b.) given that the time to exectue an algorithm with n elements is T(n) , where T(n) = T(n/2) +O(1), then the complexity of the algorithm is O(nlogn).

c.)Given a set of n numbers with range of values for 1 to n^2. Sort using counting sort will be faster than using merge sort.

d.) If the color of the root of a red black tree is changed from red to black, the red black tree property is violated.

Explanation / Answer

a) No all square number can be written as the sum of primes

for example 36 = 6 x 6

this cannot be formed by the sum of two primes

b)  given that the time to exectue an algorithm with n elements is T(n) , where T(n) = T(n/2) +O(1), then the complexity of the algorithm is O(nlogn).

True

False

Radix sort can perform better than this merge sort whose run time complexity will be O(n log n) which is reliably higher than the runtime complexity of radix sort

d.) If the color of the root of a red black tree is changed from red to black, the red black tree property is violated.

false

The property of res black tree is if the colour of the root can be changed from red to black

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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