DEV Community: Moises Gamio

Big O Notation and Analysis of Algorithms

Moises Gamio — Thu, 07 May 2026 12:42:08 +0000

Big O Notation is a mathematical notation that helps us analyze how complex an algorithm is in terms of time and space. When we build an application for one user or millions of users, it matters.

We implement different algorithms to solve one problem and measure how efficient is one respect to the other ones.

Algorithm analysis is an essential part of computational complexity theory, which aims to quantify the resources required to solve computational problems.

The first study about the Analysis of Algorithms was published by Knuth in 1968—The Art of Computer Programming.

Asymptotic Notation is used to describe the running time of an algorithm. There are three different notations: Big Omega, Big Theta, and Big O Notation.

Time complexity analysis and space complexity analysis

Time complexity analysis is related to how many steps an algorithm takes.

Space complexity analysis is related to how efficiently an algorithm uses the memory and disk.

Both terms depend on the input size, the number of items in the input. Both terms depend on the input size and the number of items in the input. Moreover, we can analyze the complexity based on three cases or asymptotic notations.:

Best case or Big Omega Ω(n): Usually the algorithm executes in one step independently of the input size.
Average case or Big Theta Θ(n): If the the input size is ramdom
Worst-case analysis or Big O Notation O(n): Gives us an upper bound on the runtime for any input. It gives us a kind of guarantee that the algorithm will never take any longer with a new input size.

Get the Job Offer, Not Just Algorithm Knowledge

Top Java Challenges: Cracking the Coding Interview: based on real interviews

I want this

Order of growth

The order of growth is related to how the runtime of an algorithm increases when the size of the input increases without limit and tells us how efficient the algorithm is.

In essence, Big O notation provides a worst-case scenario for an algorithm's performance, allowing developers to compare different algorithms and choose the most efficient one for large inputs.

Big O Notation: Common order-of-growth classifications:

Big O Notation: examples

O(1) – Constant Time Complexity

The runtime does not change with the size of the input. It does not matter if the input contains 1000 or 1 million items; the code always executes in one step.

public void constant(List<string> list, String item) {
  list.add(item);
}

In a best-case scenario, an add method takes O(1) time. The worst-case scenario takes O(n).

O(N) – Linear Time Complexity

An algorithm runs in O(N) time if the number of steps depends on the number of items included in the input. The runtime grows linearly with the size of the input.

Example: Iterating through an array or a list.

public int sum(int[] numbers) {
  int sum =0;
  for (int i =0; i<numbers.length; i++) {
    sum+=numbers[i]; // Iterating through each element
  }
  return sum;
}

In this example, if numbers has n elements, the loop executes n times, so the time complexity is O(n).

The main idea in Analysis of Algorithms is always to improve the algorithm's performance by reducing the number of steps and comparisons. You can visit find the smallest number with the same number of digits, for instance. Moreover, the simpler and more intuitive an algorithm is, the more useful and efficient it will be.

O(N²) – Quadratic Time Complexity

If an algorithm includes two loops nested in its code, we could say that it’s running in quadratic time O(N²). The runtime grows quadratically with the size of the input.

Example: When a 2D matrix is initialized in a tic-tac-toe game.

private String [][] board;

public void initializeBoard(int size) {
  this.board = new String[size][size];
  for (int x = 0; x < size; x++) {
    for (int y = 0; y < size; y++) {
      board[x][y] = " ";
    }
  }
}

Example: Nested loops iterating over the same collection

int[] arr = {1, 2, 3, 4, 5};
for (int i = 0; i < arr.length; i++) {
  for (int j = 0; j < arr.length; j++) {
    System.out.println(arr[i] + " " + arr[j]); // Nested loop
  }
}

Here, if arr has n elements, the outer and inner loops both run n times, resulting in n * n = n², so the complexity is O(N²).

O(N³) – Cubic Time Complexity

When the code includes at most three nested loops, then the algorithm runs in Cubic time.

Example: Given N integers, how many triples sum to exactly zero?. One approach (not the best) is to use three nested loops.

public int countThreeSum(int[] numbers) {
  int N =numbers.length;
  int count =0;
  for (int i = 0; i<N; i++)
    for (int j = i+1; j<N; j++)
      for (int k = j+1; k<N; k++)
        if (numbers[i] + numbers[j] + numbers[k] == 0)
          count++;

  return count;
}

O(LogN) – Logarithmic Time Complexity

This kind of algorithm produces a growth curve that peaks at the beginning and slowly flattens out as the size of the input increases. The runtime grows logarithmically with the input size.

Example: Binary search on a sorted array.

int binarySearch(int[] arr, int target) {
  int left = 0;
  int right = arr.length - 1;
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] < target) {
        left = mid + 1;
    } else {
        right = mid - 1;
    }
  }
  return -1; // Element not found
}

Log28 = 3

Log216 = 4

Log232 = 5

The binary search uses at most LogN key compares to search in a sorted array of size N. With 8 elements, it takes three comparisons, with 16 elements takes four comparisons, with 32 elements takes five comparisons, and so on.

In this example, with each iteration, the search space is halved. This results in a time complexity of O(LogN).

You can read more common Big O notations such as Linearithmic Time Complexity (O(n log n)), Exponential Time Complexity (O(2ⁿ)), and many more in the following link:

Invest in your future: master algorithms today, land the job tomorrow!

Top Java Challenges: Cracking the Coding Interview: based on real interviews

Buy Now

Summary of Big O Complexity Types:

Big O notation is essential to understand the scalability and efficiency of algorithms, especially for large datasets or performance-critical applications.

The complexity of an algorithm

To find the Big O complexity of an algorithm, follow the following rules:

Ignore the lower-order terms
Drop the leading constants

Example: If the time complexity of an algorithm is 2n³ + 4n + 3. Its Big O complexity simplifies to O(n³).

How to find the time complexity of an algorithm

Given the following algorithm:

public Integer sumEvenNumbers(Integer N) {
  int sum = 0;
  for (int number = 1; number <= N; number++)
    if ((number % 2) == 0)
      sum = sum + number;

  return sum;
}

First, we split the code into individual operations and then compute how many times it is being executed, as shown in the following table.

Description	Number of executions
int sum = 0;	1
int number = 1;	1
number <= N;	N
number++	N
if ((number % 2) == 0)	N
sum = sum + number;	N
return sum;	1

Now, we need to sum up how many times each operation is executed.

Time complexity = 1 + 1 + N + N + N + N + 1 => 4N + 3

Why Big O Notation ignores constants?

Big O Notation describes how many steps are required relative to the number of data elements. And it serves to classify the long-term growth rate of algorithms.

For instance, for all amounts of data, O(N) will be faster than O(N²) as shown in the following figure:

Now, if we compare O(100N) with O(N²), we can see that O(N²) is faster than O(100N) for some amounts of data, as shown in the following figure:

But after an intersection point, O(100N) becomes faster and remains faster (in terms of the "number of steps") for all increasing amounts of data from that point onward. And that is the reason why Big O Notation ignores constants. Because of this, the value of 100 is irrelevant and O(100N) is written as O(N). The fewer steps, the faster the algorithm.

This article was just an introduction to algorithm analysis to face an actual code interview as a software developer. They are asked to build approximated models using Big O notation in Java. The same concepts apply to Python algorithm analysis.

If you want to create a mathematical model for the execution time of a discrete operation, for example, you should take a course in discrete mathematics.

Please donate to maintain and improve this website if you find this content valuable.

Preparing to discuss algorithm analysis in your following programming interview requires practicing and studying different algorithms, and you can find it in Cracking the Coding Interview with many detailed explanations.

Understanding OOP concepts

Moises Gamio — Sat, 03 Feb 2024 17:53:41 +0000

Understanding OOP concepts gives you a solid foundation for making critical decisions about object-oriented software design.

Class

A class is a template or prototype that describes what an object will be. It defines its attributes(data) and behavior(methods). We must design a class before creating an object.

Object

An object is an instance of a class. When we create an object, we create real-world entities such as cars, bicycles, or dogs with their own attributes and own behaviors.

We instantiate an object via the new keyword in the Java programming language. When you design a class, follow the Single Responsibility Principle (SRP).

Abstraction in OOP

Abstraction allows an object telling to its users what an application does instead of how it does it. You can see the essential buttons on your TV remote control, but you don't care what happens behind when you press one of these buttons. In Java, we create abstractions via Interfaces and Abstract classes.

Encapsulation in OOP and Data Hiding

Restricting access to specific attributes and methods is called data hiding. Objects should not manipulate the data of other objects.

Encapsulation is the action of combining the data and methods in the same entity. In this way, we control access to the data in the object.

Inheritance in OOP

Inheritance is a process in which a class inherits the attributes and methods of another class.

Class inheritance in OOP provides the ability to create new classes with new functionalities while maintaining the functionalities inherited. In this way, it promotes code reusability.

This relationship is an is-a relationship because when a subclass inherits from a superclass, it can do anything that the superclass can do.

In Java, we create inheritance between classes via the extends keyword.

Polymorphism in OOP

Polymorphism in OOP means many shapes and is coupled to inheritance. For example, a Shape class defines a draw method, but Square and Circle's subclasses will implement it differently.

Composition in OOP

The composition in OOP provides a mechanism for building classes from other classes. In Java, we usually create a class with instance variables that references one or more objects of other classes.

The benefit of separating one class from another one is the Reuse.

For example, in a shopping context, we need a list of requested items and an address where to deliver the order.

public class Order {

  private int clientId;
  private List<Item> orderItems;
  private Address shippingAddress;

  //code omitted for brevity
}

We build an Item class, including an Article class.

public class Item {

  private Article article;
  private double quantity;

  //code omitted for brevity
}

And the Article class includes enough attributes to support the shopping business.

public class Article {

  private int id;
  private String name;
  private double deliveryPrice;

  //code omitted for brevity
}

We can reuse the Article class to support a Search request.

public class SearchResponse {

  private List<Article> articles;

  //code omitted for brevity
}

What happens if the business wants to introduce articles in a country where some articles are forbidden to trade?.

We can not add a new attribute called tradable to the Article class because we will never use it in normal countries.

Here, we can use the other technique to build new classes: inheritance.

Now, we can support the new requirement for the new country.

public class SearchResponse {

  private List<TradableArticle> articles;

  //code omitted for brevity
}

We can reuse our classes even out of context. For example, in a Bank context, we need an address to contact a customer.

public class Customer {

  private int customerId;
  private String lastName;
  private Address address;

  //code omitted for brevity
}

We use the term has-a to describe composition relationships. An order has-a(n) address. A customer has-a(n) address.

Software design is the art of managing dependencies and abstractions to create software that is scalable, maintainable, and efficient. This book will teach you how to design software that can handle millions of users

Learn how to manage dependencies and abstractions to create software that is flexible and adaptable

Buy Now

Advantages of object-oriented programming

Object-oriented programming (OOP) is a programming paradigm that uses objects and classes to structure code. It offers several advantages, which have contributed to its popularity and widespread use in software development:

Focuses on data: You create a program using objects focused on data. You don't define global data. Every object contains its data.
Modularity: OOP promotes modularity by encapsulating objects and their behaviors within classes. This allows developers to break down a complex system into smaller, manageable parts, making it easier to understand, maintain, and debug.
Reusability: OOP encourages code reusability through inheritance and polymorphism. Developers can create new classes by inheriting properties and behaviors from existing classes, reducing redundancy and promoting a "write once, use many times" approach.
Flexibility and Extensibility: OOP allows for easy modification and extension of existing code. You can add new classes and methods without altering the existing codebase, reducing the risk of introducing bugs in previously working code.
Abstraction: Abstraction is a key concept in OOP, where you model real-world entities as objects and focus on essential properties and behaviors while hiding unnecessary details. This simplifies problem-solving and enhances code clarity.
Encapsulation: OOP supports encapsulation by bundling data (attributes) and functions (methods) into objects. Access to an object's internal state is controlled through well-defined interfaces, promoting data integrity and security.
Organization: OOP provides a natural way to organize code, making it more intuitive for developers to work collaboratively on large projects. Classes and objects mirror the structure of the problem domain, making it easier to map real-world concepts to code.
Maintainability: OOP code tends to be more maintainable because of its modular and organized nature. Changes and updates can be made to specific classes or objects without affecting the entire system, reducing the risk of introducing unintended side effects.
Testability: OOP code is often easier to test since objects can be isolated and tested independently, leading to more comprehensive and efficient testing strategies.
Code Understandability: OOP promotes a closer alignment between code and real-world concepts, making the codebase more understandable to developers, even those who didn't write the original code.
Support for Large-Scale Development: OOP is well-suited for large-scale software development projects. Its inherent structure and organization facilitate teamwork, reduce development time, and enhance project manageability.
Community and Ecosystem: OOP has a vast and mature ecosystem of libraries, frameworks, and tools, making it easier to find resources and solutions for common programming tasks.
Cross-Disciplinary Applications: OOP applies to various domains and industries, making it a versatile paradigm suitable for a wide range of software development projects.

Understanding OOP concepts in Java or Python OOP concepts makes your system design resilient to future changes.

While OOP offers numerous advantages, it's important to note that it may not always be the best choice for every project or problem. The choice of programming paradigm should align with the specific requirements, constraints, and goals of the software being developed.

Learn how to use these concepts in SOLID design principles.

Any software design is generally a matter of opinion. There is no definitive Guide

I want this

Thank you for reading my blog. Feel free to connect on Twitter