Skip to main content

Understanding Big O Time Complexity for Beginners

Photo by Vyshnavi Bisani on Unsplash


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

Popular posts from this blog

Understanding Number Systems: Decimal, Binary, and Hexadecimal

In everyday life, we use numbers all the time, whether for counting, telling time, or handling money. The number system we’re most familiar with is the   decimal system , but computers use other systems, such as   binary   and   hexadecimal . Let’s break down these number systems to understand how they work. What is a Number System? A number system is a way of representing numbers using a set of symbols and rules. The most common number systems are: Decimal (Base 10) Binary (Base 2) Hexadecimal (Base 16) Each system has a different “base” that tells us how many unique digits (symbols) are used to represent numbers. Decimal Number System (Base 10) This is the system we use daily. It has  10 digits , ranging from  0 to 9 . Example: The number  529  in decimal means: 5 × 1⁰² + 2 × 1⁰¹ + 9 × 1⁰⁰ =  500 + 20 + 9 = 529 Each position represents a power of 10, starting from the rightmost digit. Why Base 10? Decimal is base 10 because it has 10 digits...

How to Monetize Your API as an Individual Developer While Hosting on Your Own Server?

In the API economy, cloud services like AWS, Google Cloud, and Azure offer many conveniences, such as scaling and infrastructure management. However, some developers prefer more control and autonomy, opting to host their APIs on personal servers. Whether for cost efficiency, data privacy, or customization, hosting your own API comes with both advantages and challenges. But, even without cloud platforms, there are effective ways to monetize your API. This guide will explore how individual developers can successfully monetize their APIs while hosting them on their own servers. Why Host Your API on Your Own Server? Hosting your own API gives you full control over the infrastructure and potentially lower long-term costs. Here’s why some developers choose this approach: Cost Control : Instead of paying ongoing cloud fees, you may opt for a one-time or lower-cost hosting solution that fits your budget and resource needs. Data Ownership : You have full control over data, which is critical if ...

The Weight of Responsibility: A Developer’s Journey to Balance Passion and Reality

For the past several years, Eddie has been on a steady climb in his career as a developer, but recently, he found himself at a crossroads — caught between the weight of his responsibilities and the desire to pursue his true passions. His journey began with a three-month internship as a web developer, which led to nearly four years in an application developer role. After that, he spent almost a year as a systems associate, managing tasks across systems analysis, quality assurance, and business analysis. Eventually, he returned to full-time software development for another two years before transitioning into more complex roles. For over a year, he worked as a multi-role software developer and database administrator before stepping into his current position as a senior software developer, database administrator, and cloud administrator — occasionally handling security tasks as well. Now, with over 8 years of professional experience, he also leads a small team of developers, which has been...

The Hidden Costs of Overdesign and Bad Practices in API Systems

In software development, simplicity and clarity are often sacrificed in favor of overly complex solutions. While it can be tempting to add more features and intricate designs to ensure robustness, overdesign and poor practices can have significant consequences. They frustrate developers, lead to inefficiencies, increase costs, and put unnecessary strain on system resources.  A recent example involving a team that has faced challenges with complexity highlights the pitfalls of such an approach. Overdesign: The Problem of Too Much Complexity Overdesign occurs when systems are built with more complexity than necessary. This might manifest in bloated APIs, convoluted data flows, or excessive checks and processes that don’t add substantial value. The goal is often to anticipate future problems, but this approach typically results in cumbersome systems that are difficult to maintain and scale. In one case, a company found itself paying a hefty price just to host two API services and a po...

Selenium for Beginners: What, Where, When, and Why to Use It in Automated Testing

In today’s software development landscape, automated testing has become essential for delivering robust applications efficiently. Among various automated testing tools,   Selenium   stands out as one of the most widely used and beginner-friendly options. As you embark on your journey into automated testing, it’s crucial to understand the   what, where, when, and why   of using Selenium. In this guide we will run through these essentials and help you decide if Selenium is the right tool for you. What is Selenium? Selenium  is an open-source framework used primarily for automating web browsers. It enables developers and testers to write scripts that interact with websites, simulating actions like clicking buttons, filling out forms, and navigating pages, which allows for comprehensive automated testing. Selenium supports multiple programming languages, including Python, Java, C#, and JavaScript, making it flexible for teams with different coding preferences. Key C...