Write best case, worst case and average case time complexity of following categories of algorithm–

a. Constant time

b. Linear time

c. Logarithmic time

d. Polynomial time

e. Exponential time

(this question which is where I am mostly confused as like if she had asked best case, worst case and average case of like a linear search thats easy but what this question is trying to ask is the question for me and yes i did as my teacher as said in the title)

(sorry my knowledge in dsa is quite low rn as i keep on getting 5 to 6 assignments per week and have very little time for self study)

  • $\begingroup$ (google it and find it out yourself There used to be a difference when google was younger.) $\endgroup$
    – greybeard
    Sep 4 '21 at 8:08
  • $\begingroup$ It is not entirely clear to me what the question is. Do you want an example of an algorithm that has these running times (in the best/average/worst case)? The question also isn't clear whether the examples can be reused, so I suppose you can reuse them. Finally, I'm not sure what your actual question is. You say you are confused, but what is confusing you? Can you formulate a concrete question that would clear up your confusion? $\endgroup$
    – Discrete lizard
    Sep 4 '21 at 9:13
  • $\begingroup$ @Discretelizard I think the OP is confused about it asking what are the "best case, worst case, and average case" for complexity classes rather than actual algorithms. Adam, I would recommend you to ask your teacher to clarify what it means. $\endgroup$
    – nir shahar
    Sep 4 '21 at 10:42
  • 1
    $\begingroup$ @Adam honestly, then its just a bad teacher. The role of a teacher is to teach and help the students, not to give them arbitrary tasks they don't understand and require them to solve it nonetheless. Anyways, I think its worth to at least try asking the teacher - even if he\she said they don't want "dumb doubts". For you, its totally not a dumb doubt! If you also have other colleagues who don't understand this, try to approach the teacher together with them - it will give you a higher chance of getting an actual answer. $\endgroup$
    – nir shahar
    Sep 4 '21 at 15:23
  • 1
    $\begingroup$ Emil, Juho, are you talking about the teacher's question or OP's question? The "teacher"'s question is absolutely incomprehensible. The only correct answer is "what do you mean?" OP's question is fine. $\endgroup$
    – gnasher729
    Sep 5 '21 at 9:58

Adam, the answer is that if this is indeed what your "teacher" is asking, then he doesn't have a clue. It's like "how many miles per gallon can a car do if it has (a) four gears (b) five gears (c) automatic drive" - it doesn't make any sense at all.

A correct answer would be: When we say for example that an algorithm is a "linear time algorithm", this means that the time to solve the worst case of any problem instance of size N is $\Theta(N)$, unless something else is said. For an "at most linear time algorithm" it will be $O(N)$.

This doesn't tell us anything about the best and average case, except it must be in $O(N)$ as well.


Not the answer you're looking for? Browse other questions tagged or ask your own question.