Ranter
Join devRant
Do all the things like
++ or  rants, post your own rants, comment on others' rants and build your customized dev avatar
Sign Up
Comments

Mitiko66482y@irene He probably meant after asking each half, dividing it to halfs again...
It's probably better to write O(log2 n) 
xyztrie102y@irene you would need to keep splitting up the group until you found the person who have it, and that you would do log2 n times.

okkimus21762y@irene
Overall when calculating the complexity, you take the worst case scenario in to account.
Otherwise every sorting algorithm would perform well ie if data set was already sorted. 
Root622092yAll of these assume there are 0 pens, when in reality your chances are about 75% per person.
So, O(2) average case. 
okkimus21762y@irene
Yeah actually you are right. It's wrong. The problem isn't suitable for that example. 
Huuugo26202yWithout further additions, the O notation is used to express the worst case. The best case for most of these would be O(1) except from the divide and ask method.
This all only works under the assumption there is one special pen, there is no normal human communication involved, and the OP being too lazy to search for his pen. 
Huuugo26202y@irene the whole setup doesn't make much sense, since you can't ask n people at once whether one of them has the pen. Therefore I assume the OP has a binary tree in his/her mind.
It effectively requires you to divide the group that reported positive and repeat that until there's only one person in the positive group. 
Huuugo26202y@irene if you have a group of 20 people and ask them whether one of them is having the pen, you'd probably get one answer from the person having it, rather than the whole group answering "yes" 😁
That's what doesn't make sense in the example 
Python48762yI think the O(log n) example is supposed to be dividing the class in 2 halfs then ask each half if it has a pen. Then repeat the step on that half by splitting it again into 2 halfs and ask again, till each half is made up by one person each, in which you know who has the pen.
Still doesn't make sense unless the whole class collectively shared one pen :p 
Brolls34292yHoly shit. I’ve literally never understood time complexity sand every example has never illustrated it for me.
This has pleased me.
Related Rants
Asymptotic complexities
Finding a pen in a classroom of n students
O(n^2)  Asking each student and ask him about others too
O(n)  Asking each student
O(logn)  Dividing class equally and asking each half
O(1)  Damn it, I have it in my pocket 😂😂
rant
complexity
algorithms