For each of the following functions, specify an algorithm with the that function

Question

For each of the following functions, specify an algorithm with the that function as the worst-case time complexity in the sense of big THETA.

1. g(n) = n3
2. f(n)=n4logn

3. h(n)=logn

4. j(n) = n2
5. k(n) = n2n

Here when I say specify, you might refer to a well-known algorithm such as grade-school addition of two positive integers written in decimal notation with n as the number of digits in the largest integer input or provide pseudo- code. You should also make it clear how you are measuring the size of the input (i.e. what does n mean) and your n should not be a bizarre measure; do not use n = mlogm for measuring the size of an m by m matrix for exam- ple. Lastly you need to make clear how you are measuring time complexity. And again pick a natural measure such as the number of comparison when analyzing a sorting algorithm; do not use the cube root of the number of comparisons for example.

Explanation / Answer

1) Naive multiplication of two matrices of nXn takes O(n3).

In this the number of additions and multiplications are n3.

2) There is no standard algorithm which follows O(n4logn) but one niche algorithm which is using fast-fourier transformation, convolution, and pre-computation to compute the distance correlation between all pairwise windows is O(n4logn).

3) Binary search takes time logn where n is the size of sorted array.

In this the number of comparisons are logn

4) Bubble sort takes time n2.

In this the number of comparisons is n2.

5) Not clear what you have written n2n is n3 which is already part 1.

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

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