366

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 😂😂

Comments
  • 9
    brilliant hahaha
  • 14
    Nice one, this amused my integrated circuits!
  • 7
    @irene He probably meant after asking each half, dividing it to halfs again...

    It's probably better to write O(log2 n)
  • 2
    @irene I guess no.
  • 5
    @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.
  • 2
    @irene good point.
  • 10
    @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.
  • 7
    O(0) -- realizing you don't care because you type everything anyway.
  • 2
    @irene Only if you own a pen and think about using it!
  • 4
    So underrated. This pun deserves much more ++
  • 4
    O(2^n) : asking each combination of groups of students if they have a pencil.
  • 1
    All of these assume there are 0 pens, when in reality your chances are about 75% per person.

    So, O(2) average case.
  • 2
    @irene
    Yeah actually you are right. It's wrong. The problem isn't suitable for that example.
  • 1
    @irene well ofc lol
  • 1
    Without 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.
  • 3
    @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.
  • 2
    @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
  • 1
    @paranoidAndroid your integral circuits are sparking? 😂
  • 2
    @enoon bzzzzzzzz bz bzz
  • 4
    I 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
  • 4
    Holy shit. I’ve literally never understood time complexity sand every example has never illustrated it for me.

    This has pleased me.
Add Comment