write whether the following statements are true or false. If true, prove why it

Question

write whether the following statements are true or false. If true, prove why it is true. If false, give a counter example or proof (2+6)*=48

a) all square numbers can be written as the sum of two primes ( e.g. 4=3+1, 25=23+2)

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

c) given a set of n numbers with range of values for 1 to n^2 sorting using counting sort will be faster than sorting 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) False

Lets see the squares pattern

4 = 3+1

9 = 2+7

16 = 11 + 5

25 = 2 + 23

36 = 13 + 23

49 = 2 + 47

64 = 17 + 47

81 = 2 + 79

100 = 3 + 97

121 impossible

121 cannot be written as sum of 2 primes for example 2 and 119 can be a combination but 119 is not a prime and 121 is an odd number so to form an odd number one even number and one add number sum will only result in an odd number, 2 is the only even prime number, hence for 121 statement (a) contradicts

b) False

T(n) = T(n/2) + O(1)

Applying Masters therorem i.e, T(n) = aT(n / b) + nc

Here we have a = 1, b=2 and c=0

since c =  logba here c =0 ==> (0 = log2 1)

which holds true hence we are in case-2 of Masters theorem

==> (nclog n) = (n0 log n) = (log n).

==> O(logn)

we can solve this without using the theorem, here is the solution without using theorem

T(n)=T(n/2)+O(1)

T(n/2)=T(n/4)+O(1)

..

..

T(2)=T(1)+O(1)

T(1)=O(1)

Hence,T(n)=O(1) * log n

Hence,T(n)=O(1) * log n

=>T(n)=O(logn)

here log is of base 2

c) False

Counting sort will take a complexity of O(n2) where as Merge sort will take O(nlogn)

Counting sort will be effective if it is in the range of known range 0 - n-1 , here the range is from 1 - n2

Hence merge sort is faster compared to counting sort in this case.

How ever using Radix sort we can achieve O(n) complexity

d)False

These are the properties of Red Black Trees

1) Every node has a color either red or black.

2) Root of tree is always black.

3) There are no two adjacent red nodes (A red node cannot have a red parent or red child).

4) Every path from root to a NULL node has same number of black nodes.

so here when red root is changed to black , it will satisfy second property

and as the red is changed to black so property 3 is also not gonna disturb

Hence it doesnt violate

Hope this answer helps you. Have a good chegging. You can always post your comments if you have any doubts, ready to help you anytime.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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