How to give mathemarical proof or support my answer through reasoning as a general case?

Question

You are managing a software project that involves building a computer-assisted instrument for medical surgery. The exact placement of the surgical knife is dependent on a number of different parameters, usually at least 25, sometimes more. Your programmer has developed two algorithms for positioning the cutting tool, and is seeking your advice about which algorithm to use:

Algorithm A has an average – case run time of n, and a worst case run time of n^4, where n is the number of input parameters.

Algorithm B has an average case run time of n[(log n)^3], and a worst case of n^2. Which algorithm would you favour for inclusion in the software? Justify your answer.

I think i should choose algorithm 1 because in medical science we must be more focused towards saving life of more people hence average case should be better however for worst case we can apply some optimization to work better or we can choose algorithm 2. But i m confused how to proof it Mathematically that i am correct.

For all interested readers. However i have marked first answer good but actually to get all the perspective do read comments and second answer.

25 is a tiny value for 'n'; any constant factor in the actual calculation could easily dwarf even n^4. The answer to which algorithm should be the one that's easiest to write, read and maintain. Has he profiled the code for each algorithm? Does it meet the acceptance criteria for performance? These are the practical questions you will face in the real world. — Ian Mercer, Jun 15 '15 at 05:37
log n is usually small, and (roughly speaking) ignorable in practical applications. However, in your case, log 25 < 5 (base 2 logarithm). n (log n)^3 < 25 * 125 = 3125 which is bigger than n^2 = 625 (worst case running time). So worst case time is better than average case. ? In any case n^4 dwarfs n^2 in size, so it's by far the worst choice. — Edward Doolittle, Jun 15 '15 at 05:46
@EdwardDoolittle good observation bro in medical we should account for worst case. Logn observation is good . Thanks.. — Arjun Chaudhary, Jun 16 '15 at 02:16

score 2 · Answer 1 · answered Jun 15 '15 at 05:26

I think for starters you need to determine what the time needed for the average surgical procedure is going to be. Obviously, if either O(n) or O(n*(log_n)^3) be significantly slower than the average procedure time then neither will do. If the former suffices but the latter would result in either lost lives or an unacceptable user experience, then you can rule out the latter algorithm. Assuming that both these running times will meet the average demand, then the next thing to examine is the worst case running time. The O(n) algorithm has a stiff penalty when running at its worst - O(n^4), while the O(n*(log_n)^3) runs at only O(n^2) at its worst. For every surgical procedure in your data set, you should examine how long the patient can survive before receiving the surgery, for each algorithm in the worst case. If many lives would potentially be lost due to a potential O(n^4) performance, then you may rule out this algorithm.

So I would recommend focusing on the two benchmarks for what is acceptable for average time and the worst case scenario and go from there. — Tim Biegeleisen, Jun 15 '15 at 09:46

score 2 · Accepted Answer · edited May 23 '17 at 12:06

2

This would be a hard real-time system - if a deadline is missed then a patient might die. As such, Algorithm B is the preferred algorithm because you can design the hardware around the n^2 worst case, whereas with Algorithm A the hardware must account for the n^4 worst case (the average case doesn't matter because the system is ostensibly intended to save every patient's life, not 80% of the patient's lives).

This assumes that the hardware budget is not a factor. If the hardware budget is a factor (e.g. the machines are intended to be sold to facilities that are short on funds) then Algorithm A is preferred because the hardware can be designed for the n average case - this will result in patient deaths in the n^4 case, but presumably more patients will be saved by use of the machines. However, this is getting outside the scope of computer science and more into the scope of ethics - my preferred answer would be to select Algorithm B and pay for decent hardware.

edited May 23 '17 at 12:06

Community

1
1

answered Jun 15 '15 at 05:37

Zim-Zam O'Pootertoot

17,888
4
41
69

1

I agree with your answer, but I might say that worst case running time is n^4 not O(n^4). O(n^4) is asymptotic complexity, meaning the tendency for very large n. Here that's not an issue: it's actual running time for all cases. – Edward Doolittle Jun 15 '15 at 05:40
@EdwardDoolittle Fixed – Zim-Zam O'Pootertoot Jun 15 '15 at 05:42
Your and above person explanation together form right answer because i also think question should have stated what is machine deadline or critical time. – Arjun Chaudhary Jun 15 '15 at 09:48
So i think instead writing in support of one i should think of adv and disadv of both algo. – Arjun Chaudhary Jun 15 '15 at 09:49

How to give mathemarical proof or support my answer through reasoning as a general case?

2 Answers2