Curry
  • Curry
Question on combinatorics. No clue where to start. Any help much appreciated!!
Mathematics
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
jamiebookeater
  • jamiebookeater
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
Curry
  • Curry
1 Attachment
Curry
  • Curry
@AravindG
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
  • Curry
@ganeshie8 can you help me out here? having really hard time to get started. :/
ganeshie8
  • ganeshie8
try @dan815
dan815
  • dan815
xD so much reading
dan815
  • dan815
if u break it down and ask me a particular question on it, maybe i can help uq
Curry
  • Curry
Hello, so here is my answer for part 1. Can you please tell me if it is right?
1 Attachment
Rizags
  • Rizags
i can only help with the second part as I am unsure of the first
Curry
  • Curry
Well for the first group, i checked 6 times. 0 times for the 2nd group. 4 times for the last group.
Curry
  • Curry
yes, i understand how the split works.
dan815
  • dan815
okay sooo dooo ittttttttttt
Curry
  • Curry
that gives me 12.
Curry
  • Curry
i mean, 6*
dan815
  • dan815
hmm wait okay
dan815
  • dan815
http://prntscr.com/92kf4r
Curry
  • 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
  • dan815
okay that is what ur doing
Curry
  • Curry
?
dan815
  • dan815
can u delete stuff its lagigng me
dan815
  • dan815
okay ill just show u >_>
Curry
  • Curry
which stuff? comments?
dan815
  • dan815
nvm its fine now
dan815
  • dan815
|dw:1447483308419:dw|
dan815
  • dan815
there can be a total of k infected in the first group itself
dan815
  • dan815
so u will perform binary search on the group n/k, k times in worst case scenario
dan815
  • dan815
each time removing 1 sameple
Curry
  • Curry
mhmm
dan815
  • dan815
|dw:1447483442717:dw|
dan815
  • dan815
this is an upper bound
dan815
  • 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
  • Curry
Oh kk. So that, formula works?
dan815
  • dan815
yes its just an upper bound
dan815
  • dan815
there are multiple upper bounds u can find, its just what s the closest upperbound
dan815
  • dan815
i advise u to find a better one
dan815
  • dan815
just make sure atleast that park makes sense
dan815
  • dan815
part*
dan815
  • dan815
|dw:1447483659439:dw|
Curry
  • Curry
so it's a ceiling function?
dan815
  • dan815
yes
dan815
  • dan815
oh um that shud be n/k
dan815
  • dan815
|dw:1447483946957:dw|
dan815
  • 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
  • Curry
wait, isn't upper bound supposed to be in theta format?
dan815
  • dan815
in big O notation?
dan815
  • dan815
can u show some work or attempts
Curry
  • Curry
What do you mean? And also, shouldn't the coefficient in front of the summation be n/k and not just k?
dan815
  • dan815
hm
dan815
  • dan815
why?
Curry
  • 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
  • dan815
hmm
dan815
  • dan815
|dw:1447484301776:dw|
dan815
  • dan815
think about this case
dan815
  • dan815
N samples and N-1 infections
dan815
  • dan815
or N samples and N infections u dont know that there were N infections
dan815
  • dan815
so for each group, ud have to perform N/K binary searches
dan815
  • dan815
so for K groups ull perform N/k binary searches on elements N/k as they decrease by 1 every time
Curry
  • Curry
OOO. gotchya gotchya.
Curry
  • Curry
And why not just use a celing bracket instead of R for rounding up? is that just your convention? just wondering.
Curry
  • Curry
So wait, in the diagram yu drew, that implies 2 possible upper bounds. But there can only be one answer though.
dan815
  • dan815
i dunno the symbol for ceiling lol
dan815
  • dan815
|dw:1447484936455:dw|
Curry
  • Curry
|dw:1447484936290:dw|
Curry
  • Curry
that'd be the symbol for ceiling. those brackets flipped downwards would be floor.
Curry
  • Curry
But um, my question still persists. Can we have 2 aanswer for upper bound? i thought, only one answer can exist.
dan815
  • dan815
um
dan815
  • dan815
ya there are like multiple answers for an upper bound
dan815
  • dan815
liek 2<3 also 2<4 2<10.... its just what is the closest possible upper bound
dan815
  • dan815
|dw:1447485596386:dw|
dan815
  • dan815
i mean do u get this so far?
Curry
  • Curry
yes.
dan815
  • dan815
u can make it a better function of k u see
dan815
  • 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.