KwickClips Java · 41 sec · free
Is linear search O(1) because it once found the item first?
Short answer. No, that is only its best case. The worst case is O(n).
Why do exams ask for the worst case?
It is a guarantee that the program will never be slower.
Linear search cases
| Case | When | Big O |
|---|---|---|
| Best | item first | O(1) |
| Average | middle | O(n) |
| Worst | last, missing | O(n) |
Remember
| Best: fewest steps |
| Worst: most steps, a guarantee |
Linear search found it first time. Is it order one? Only in the best case. If the item is last or missing, it is the worst case, order n. Average is also order n. Best means fewest steps. Worst means most steps, and it is a guarantee.
This clip is from the full lesson: Algorithm Complexity and Big O Notation — 7 minutes, with the tables, the quick answers and the whole lesson in text.
Useful for: ISC Class 12 Computer Science (868), ISC Class 12 Computer Science (868), ISC Class 12 Computer Science (868), ISC Class 12 Computer Science (868)
More KwickClips from this lesson
Why not just time the program with a stopwatch?40 sec
What is the Big O of 3n² + 5n + 9?41 sec
What is the Big O of two separate loops, one after the other?38 secVoice-over is AI-generated; the script is written and checked by Kajal Ma'am. Confirm anything you plan around against your official board document. We never ask for a password or an OTP.