# Worst Case Time Complexity - Maximum Run Time | Discrete Further Maths ASWatch

Announcements
#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).

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
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
X

new posts
Latest
My Feed

### Oops, nobody has postedin the last few hours.

Why not re-start the conversation?

see more

### See more of what you like onThe Student Room

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

### University open days

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

### Poll

Join the discussion

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%