KwickClips Java · 38 sec · free
What is the Big O of two separate loops, one after the other?
Short answer. Still O(n), because n + n is O(n).
Which loop shape gives O(log n)?
One that doubles or halves i each time.
Loop shapes
| Loop | Big O |
|---|---|
| Single loop | O(n) |
| Loop in loop | O(n²) |
| i = i / 2 | O(log n) |
Remember
| Nested loops multiply |
| Halving gives log n |
Can you read Big O just by looking at loops? A single loop to n is order n. A loop inside a loop is order n squared. A loop that halves i is order log n. Nested loops multiply. Halving gives log n.
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
Is linear search O(1) because it once found the item first?41 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.