Worst Case Time Complexity - Maximum Run Time | Discrete Further Maths AS Watch

bfm.mcdermott
Badges: 20
Rep:
?
#1
Report Thread starter 1 week ago
#1
I have my Further Maths Discrete AS paper tomorrow but when going through the spec one last time, I realised I don't know how to calculate the maximum run time (e.g. for a specific shuttle sort problem).

The spec says: Calculate worst case time complexity, the 'maximum run time' T(n), as a function of the size of a problem in simple cases by considering the worst case for a specific problem.

Can anyone tell me how to do this?

An example question is:
Shuttle sort and bubble sort are each used to sort this list into decreasing order. 4, 6,12,37,2,9.
(i) Count the total number of comparisons and the total number of swaps used when shuttle sort is used.
(ii) Count the total number of comparisons and the total number of swaps used when bubble sort is used.
(iii) For this particular list, which of the two algorithms will complete the sort in the shorter time?
(iv) Find an expression for the worst case time complexity, T(n), for shuttle sort.
(v) Show that the efficiency of bubble sort is O(n2).
(vi) A computer using bubble sort takes 0.4 seconds to sort a list of 100 numbers. Estimate how long it will take to sort a list of 500 numbers.

I can use shuttle sort and bubble sort okay but I don't know how to answer part (iv).

The answer is:
Spoiler:
Show
(iv) In the worst case (when the original list is in the reverse order to the final list) shuttle sort uses 1 + 2 + 3 + … + (n-1) = comparisons, for a list of length n, and the same number of swaps. However much time a swap and a comparison take, the time taken will be some multiple of, so T(n) = for a constant k.

Any advice or explanation at all is gratefully received as I'm panicking now. Thanks!
Last edited by bfm.mcdermott; 1 week ago
0
reply
DFranklin
Badges: 18
Rep:
?
#2
Report 1 week ago
#2
Try running through the algorithm for an example such as sorting 5,4,3,2,1 into ascending order; it should become fairly obvious why the costs of the 'rounds' goes up by 1 each time.
0
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Latest
My Feed

See more of what you like on
The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

Personalise

University open days

  • SOAS University of London
    Postgraduate Open Day Postgraduate
    Wed, 29 May '19
  • University of Exeter
    Undergraduate Open Day - Penryn Campus Undergraduate
    Thu, 30 May '19
  • Cranfield University
    Cranfield Forensic MSc Programme Open Day Postgraduate
    Fri, 31 May '19

How did your AQA A-level Business Paper 1 go?

Loved the paper - Feeling positive (228)
22.69%
The paper was reasonable (453)
45.07%
Not feeling great about that exam... (181)
18.01%
It was TERRIBLE (143)
14.23%

Watched Threads

View All
Latest
My Feed

See more of what you like on
The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

Personalise