analyzing worse case in a linear time selection

43 Views Asked by At

I have a question I'm trying to figure out. I don't have any good sources or examples so I found an example to go off of provided by Bowdoin College. Below is my attempt to solve this problem based on that source.

Specifically what I was looking for is:

  1. Did I do everything right (i.e. is my answer correct)?

  2. Is my step 5 math correct (each of the two num elements & my Induction)?

  3. I finally found a constant c = 201 and n = 538 that satisfies my inequality of:

    101c + n <= (24/101)cn

But i just kept plugging in numbers for c and n until I found a pair that worked. Is there a more efficient and easier way to do this, then trial by error?


Question and answer

enter image description here