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 secDisclaimer. KwickAcademy is free study material for general learning and revision. Parts of it, including the voice-over, are produced with the help of AI tools and may contain errors; if you spot one, please tell us and we will correct it. Syllabus, marks and exam details follow the latest official board publications available to us, and boards can change them at any time, so always confirm against your board's official website and your school. Using this material does not guarantee any marks or result. Board names and trademarks belong to their owners; Kwickprep is not affiliated with or endorsed by any examination board. We never ask for passwords, OTPs or ID numbers. Your progress is saved only in this browser. Full disclaimer · Privacy