simple algorithm - repost

£10-20 GBP

Ditutup

Disiarkan

sekitar 10 tahun yang lalu

£10-20 GBP

Dibayar semasa penghantaran

I need this question answered. A “Hybird” sorting algorithm based on QuickSort or Merge Sort, which are both O(n log n), could use a simple algorithm like “insertion sort” for a finite number of cases with small n. Use the “Big O” notation to demonstrate that the time complexity of such a hybrid algorithm is still O(n log n) when it is based on QuickSort even though it uses O(n^2) “insertion sort” for cases where n ≤ m = 20

Mathematics

ID Projek: 5433057

Tentang projek

8 cadangan

Projek jarak jauh

Aktif 10 tahun yang lalu

Ingin menjana wang?

Alamat e-mel

Faedah membida di Freelancer

Tetapkan bajet dan garis masa anda

Dapatkan bayaran untuk kerja anda

Tuliskan cadangan anda

Ianya percuma untuk mendaftar dan membida pekerjaan

8 pekerja bebas membida secara purata £42 GBP untuk pekerjaan ini

@Calleus

Hi, I have strong background in Algorithms design and its complexity. Let me help you. I am ready to start.

£63 GBP dalam 3 hari

4.8

(32 ulasan)

5.6

@itachi23

A proposal has not yet been provided

£63 GBP dalam 2 hari

4.9

(24 ulasan)

5.0

@Monkeypuzzler

The problem is easy. I'll outline the solution here, and then appeal to your conscience to square up afterwards. The answer is almost immediate from the definition of Big O notation, and has nothing to do with the growth of the special case for n<20; "f(n)=O(g(n)) if there exist a constant a>0 and N>0 such that f(n)<a*g(n) when n>N". So if you pick out some finite number e.g. 20 so that you use a different algorithm on for n < 20, then it makes no difference. Formally, if T(n) is the cost of your new algorithm, you know that, because for n>20 it is O(n log n), there exists N>0 and a>0 such that T(n)<a*n log n for n>N. Choose M=max(20,N). Then T(n)<a*n log n for n>M, and so as there exist M>0 and a>0 such that T(n)<a*n log n for n>M, T(n)=O(n log n).

£10 GBP dalam 1 hari