When you hear about Big O notation, it may sound like an intimidating concept reserved for mathematicians and computer scientists. However, it’s one of the most important tools for evaluating how efficiently algorithms run as the size of their input grows.
In this guide, we’ll break down the most common types of Big O time complexities, explain them in simple terms, and provide Kotlin code examples that you can run in the Kotlin Playground to better understand each concept.
What is Big O Notation?
Big O notation describes how the runtime or space requirements of an algorithm grow relative to the input size. It’s a way to compare the efficiency of different algorithms regardless of hardware or implementation details.
Big O focuses on worst-case scenarios to help predict the performance of an algorithm.
Common Types of Big O
Here are the most common types of Big O complexities and what they represent:
O(1) — Constant Time
- Growth: Runtime remains the same regardless of input size.
- Description: No matter how large the input is, the execution time does not change.
- Example: Returning a single value or accessing an array element by index.
O(n) — Linear Time
- Growth: Runtime grows proportionally with the input size.
- Description: The algorithm processes each element exactly once.
- Example: Summing all elements in an array.
O(n²) — Quadratic Time
- Growth: Runtime grows proportionally to the square of the input size.
- Description: Often involves nested loops over the same input.
- Example: Comparing all pairs of elements, as in basic sorting algorithms like Bubble Sort.
O(n³) — Cubic Time
- Growth: Runtime grows proportionally to the cube of the input size.
- Description: Adds an additional nested loop, making operations more computationally expensive.
- Example: Processing elements in a 3D matrix.
O(n*m) — Rectangular Time
- Growth: Runtime depends on two different input sizes.
- Description: Involves two loops with independent input sizes.
- Example: Comparing two arrays of different lengths.
O(log n) — Logarithmic Time
- Growth: Runtime grows very slowly as the input size increases.
- Description: Divides the problem size in half at each step.
- Example: Binary search.
O(n log n) — Linearithmic Time
- Growth: Runtime grows faster than linear but slower than quadratic.
- Description: A combination of linear iteration and logarithmic division.
- Example: Merge Sort and QuickSort (average case).
O(2ⁿ) — Exponential Time
- Growth: Runtime doubles with each additional input element.
- Description: Common in recursive algorithms that solve subproblems independently.
- Example: Recursive solutions to the Towers of Hanoi or Fibonacci sequence.
O(n!) — Factorial Time
- Growth: Runtime grows astronomically with input size.
- Description: Explores all possible permutations of the input.
- Example: Solving the Traveling Salesman Problem or generating permutations.
Examples with Kotlin Code
Below is Kotlin code demonstrating each time complexity. Run this code in the Kotlin Playground to see how different types of complexities behave.
fun main() {
println("\nO(1): Constant Time Example")
measureExecutionTime { println(constantTime()) }
println("\nO(n): Linear Time Example")
measureExecutionTime { linearTime(20) }
println("\nO(n^2): Quadratic Time Example")
measureExecutionTime { quadraticTime(10) }
println("\nO(n^3): Cubic Time Example")
measureExecutionTime { cubicTime(10) }
println("\nO(n*m): Rectangular Time Example")
measureExecutionTime { rectangularTime(10, 20) }
println("\nO(log n): Logarithmic Time Example")
measureExecutionTime { logarithmicTime(10) }
println("\nO(n log n): Linearithmic Time Example")
measureExecutionTime { linearithmicTime(10) }
println("\nO(2^n): Exponential Time Example")
measureExecutionTime { exponentialTime(10) }
println("\nO(n!): Factorial Time Example")
measureExecutionTime { factorialTime(6) }
}
// Utility function to measure and display execution time
fun measureExecutionTime(block: () -> Unit) {
val start = System.nanoTime()
block()
val end = System.nanoTime()
val duration = end - start
println("Execution time: ${duration / 1_000_000.0} ms")
}
// O(1): Constant Time
fun constantTime(): String {
return "Here's your cookie 🍪!"
}
// O(n): Linear Time
fun linearTime(n: Int) {
println("Walking through $n rooms...")
for (i in 1..n) {
println("👋 Hi from room $i!")
}
}
// O(n^2): Quadratic Time
fun quadraticTime(n: Int) {
println("Shaking hands at a party of $n people...")
for (i in 1..n) {
for (j in 1..n) {
print("🤝 Person $i meets Person $j ")
}
println()
}
}
// O(n^3): Cubic Time
fun cubicTime(n: Int) {
println("Building a 3D cube with $n layers...")
for (i in 1..n) {
for (j in 1..n) {
for (k in 1..n) {
print("🧱($i,$j,$k) ")
}
println()
}
println("--- Finished layer $i ---")
}
}
// O(n*m): Rectangular Time
fun rectangularTime(n: Int, m: Int) {
println("Matching $n shirts with $m pants...")
for (i in 1..n) {
for (j in 1..m) {
print("👕 Shirt $i + 👖 Pants $j ")
}
println()
}
}
// O(log n): Logarithmic Time
fun logarithmicTime(n: Int) {
println("Finding a treasure in a chest with $n locks...")
var i = n
var step = 0
while (i > 1) {
i /= 2
step++
println("🔓 Step $step: Open half, $i locks left")
}
println("🎉 Found the treasure!")
}
// O(n log n): Linearithmic Time
fun linearithmicTime(n: Int) {
println("Sorting $n toy boxes...")
for (i in 1..n) {
var j = i
var step = 0
while (j > 1) {
j /= 2
step++
println("📦 Toy box $i, Sorting step $step")
}
}
}
// O(2^n): Exponential Time
fun exponentialTime(n: Int) {
println("Answering $n questions with 'yes' or 'no'...")
fun helper(steps: Int, path: String = "") {
if (steps == 0) {
println("Path: $path")
return
}
helper(steps - 1, "$path Yes")
helper(steps - 1, "$path No")
}
helper(n)
}
// O(n!): Factorial Time
fun factorialTime(n: Int) {
println("Seating $n friends in all possible ways...")
fun helper(permutation: String, remaining: String) {
if (remaining.isEmpty()) {
println("🪑 Arrangement: $permutation")
return
}
for (i in remaining.indices) {
helper(
permutation + remaining[i],
remaining.substring(0, i) + remaining.substring(i + 1)
)
}
}
helper("", "ABCDEFGHIJ".take(n))
}Conclusion
Understanding Big O notation is essential for designing efficient algorithms. While it can be daunting at first, visualizing these complexities through examples makes them much easier to grasp. Experiment with the provided Kotlin code, tweak the input sizes, and observe how runtime changes.
Comments
Post a Comment