Question on combinatorics. No clue where to start. Any help much appreciated!!

- Curry

Question on combinatorics. No clue where to start. Any help much appreciated!!

- Stacey Warren - Expert brainly.com

Hey! We 've verified this expert answer for you, click below to unlock the details :)

- jamiebookeater

I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!

- Curry

##### 1 Attachment

- Curry

@AravindG

- AravindG

Sorry I havent done combinatorics in years. Let's see if someone else can put some light here.

Looking for something else?

Not the answer you are looking for? Search for more explanations.

## More answers

- Curry

@ganeshie8 can you help me out here? having really hard time to get started. :/

- ganeshie8

try @dan815

- dan815

xD so much reading

- dan815

if u break it down and ask me a particular question on it, maybe i can help uq

- Curry

Hello, so here is my answer for part 1. Can you please tell me if it is right?

##### 1 Attachment

- Rizags

i can only help with the second part as I am unsure of the first

- Curry

Well for the first group, i checked 6 times. 0 times for the 2nd group. 4 times for the last group.

- Curry

yes, i understand how the split works.

- dan815

okay sooo dooo ittttttttttt

- Curry

that gives me 12.

- Curry

i mean, 6*

- dan815

hmm wait okay

- dan815

http://prntscr.com/92kf4r

- Curry

uM, I have to submit this hw by 12 am and it's 10:40pm. Is it ok if Ganeshie chips in too? He said he was familiar with this problem. :/

- dan815

okay that is what ur doing

- Curry

?

- dan815

can u delete stuff its lagigng me

- dan815

okay ill just show u >_>

- Curry

which stuff? comments?

- dan815

nvm its fine now

- dan815

|dw:1447483308419:dw|

- dan815

there can be a total of k infected in the first group itself

- dan815

so u will perform binary search on the group n/k, k times in worst case scenario

- dan815

each time removing 1 sameple

- Curry

mhmm

- dan815

|dw:1447483442717:dw|

- dan815

this is an upper bound

- dan815

but its kinda weird to see this because its not really even possible, u wont even do this many things if u are finding samples like that

- Curry

Oh kk. So that, formula works?

- dan815

yes its just an upper bound

- dan815

there are multiple upper bounds u can find, its just what s the closest upperbound

- dan815

i advise u to find a better one

- dan815

just make sure atleast that park makes sense

- dan815

part*

- dan815

|dw:1447483659439:dw|

- Curry

so it's a ceiling function?

- dan815

yes

- dan815

oh um that shud be n/k

- dan815

|dw:1447483946957:dw|

- dan815

u are doing binary search on each group, and at most ud have to do binary search k times on a single group

- Curry

wait, isn't upper bound supposed to be in theta format?

- dan815

in big O notation?

- dan815

can u show some work or attempts

- Curry

What do you mean? And also, shouldn't the coefficient in front of the summation be n/k and not just k?

- dan815

hm

- dan815

why?

- Curry

cause initially i thought there should be no coefficient. But if there is going to be any, and based on your explanation that there are n/k groups and we're iterating through them each time, i thought it should be n/k

- dan815

hmm

- dan815

|dw:1447484301776:dw|

- dan815

think about this case

- dan815

N samples and N-1 infections

- dan815

or N samples and N infections u dont know that there were N infections

- dan815

so for each group, ud have to perform N/K binary searches

- dan815

so for K groups ull perform N/k binary searches on elements N/k as they decrease by 1 every time

- Curry

OOO. gotchya gotchya.

- Curry

And why not just use a celing bracket instead of R for rounding up? is that just your convention? just wondering.

- Curry

So wait, in the diagram yu drew, that implies 2 possible upper bounds. But there can only be one answer though.

- dan815

i dunno the symbol for ceiling lol

- dan815

|dw:1447484936455:dw|

- Curry

|dw:1447484936290:dw|

- Curry

that'd be the symbol for ceiling. those brackets flipped downwards would be floor.

- Curry

But um, my question still persists. Can we have 2 aanswer for upper bound? i thought, only one answer can exist.

- dan815

um

- dan815

ya there are like multiple answers for an upper bound

- dan815

liek 2<3
also 2<4
2<10....
its just what is the closest possible upper bound

- dan815

|dw:1447485596386:dw|

- dan815

i mean do u get this so far?

- Curry

yes.

- dan815

u can make it a better function of k u see

- dan815

this covered alll the worst possible cases for K

Looking for something else?

Not the answer you are looking for? Search for more explanations.