DZone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
Refcards Trend Reports Events Over 2 million developers have joined DZone. Join Today! Thanks for visiting DZone today,
Edit Profile Manage Email Subscriptions Moderation Admin Console How to Post to DZone Article Submission Guidelines
View Profile
Sign Out
Refcards
Trend Reports
Events
Zones
Culture and Methodologies Agile Career Development Methodologies Team Management
Data Engineering AI/ML Big Data Data Databases IoT
Software Design and Architecture Cloud Architecture Containers Integration Microservices Performance Security
Coding Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Partner Zones AWS Cloud
by AWS Developer Relations
Culture and Methodologies
Agile Career Development Methodologies Team Management
Data Engineering
AI/ML Big Data Data Databases IoT
Software Design and Architecture
Cloud Architecture Containers Integration Microservices Performance Security
Coding
Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance
Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Partner Zones
AWS Cloud
by AWS Developer Relations
Building Scalable Real-Time Apps with AstraDB and Vaadin
Register Now

Trending

  • Revolutionizing Algorithmic Trading: The Power of Reinforcement Learning
  • Operator Overloading in Java
  • Authorization: Get It Done Right, Get It Done Early
  • How to LINQ Between Java and SQL With JPAStreamer

Trending

  • Revolutionizing Algorithmic Trading: The Power of Reinforcement Learning
  • Operator Overloading in Java
  • Authorization: Get It Done Right, Get It Done Early
  • How to LINQ Between Java and SQL With JPAStreamer
  1. DZone
  2. Data Engineering
  3. Data
  4. Big O Notation - Why? When? Where?

Big O Notation - Why? When? Where?

Why? Big O notation gives abstraction and the opportunity for generalizing. When? Whenever you want to measure one parameter from the changing volume of another. Where? It is best to look at fairly atomic sections of code that make one specific business logic.

Danylo Tolmachov user avatar by
Danylo Tolmachov
·
Nov. 22, 22 · Tutorial
Like (6)
Save
Tweet
Share
5.64K Views

Join the DZone community and get the full member experience.

Join For Free

What Is Big O?

This is a mathematical term that originated in the early 20th century in number theory and came almost immediately to computer science as questions arose with resource optimization. Wiki-defined Big O notation is a mathematical notation that describes the limiting behaviour of a function when the argument tends towards a particular value or infinity. Let's rephrase it, and make this definition a little simpler and closer to software development. Any task is solved according to one or another approach, one or another algorithm of action. To compare the effectiveness of heterogeneous solutions written in different programming languages using different approaches, you can start analyzing its execution through the notation. Next, let's look at the most common classes of frequently encountered time complexities.

O(1) - Сonstant

O(1) - Сonstant

Nothing depends on the volume of input data, most likely the manipulation will not be performed on the entire volume, but a certain fixed part of them will be selected

Code example

JavaScript
 
const array = [1, 2, 5, 8, 100]
console.log(array[0]) // 1

As an example, it is straightforward access to array elements. Unfortunately, there is no good example in algorithms. As you can see it is a pretty simple action, not sure if this could be named an algorithm.


O(n) - Linear 

O(n) - Linear

The complexity of the algorithm increases predictably and linearly with the amount of input. Accordingly, the efficiency of such an algorithm falls in direct proportion.

Code example

JavaScript
 
const array = [1, 2, 3, 4, 5]
let sum = 0
for (let i = 0; i < array.length; i++) {
  sum += array[i] 
}

console.log(sum) // 15

As an algorithm example, here we could look at linear search. It is like a brute-force search by going through elements one by one from one end to another.


O(n^2) - Quadratic

O(n^2) - Quadratic


The complexity of the algorithm implies passing through the data sample twice to get the result.

JavaScript
 
const matrix = [
  [1, 2, 3],
  [1, 2, 3],
  [1, 2, 3],
]

let sum = 0
for (let i = 0; i < matrix.length; i++) {
  for (let j = 0; j < matrix[i].length; j++) {
    sum += matrix[i][j]
  }
}

console.log(sum) // 18

Among algorithms, many simple sorts satisfy such complexity. For example, Bubble sort and Insertion sort.


 O(log n) - Logarithmic

O(log n) - Logarithmic


The main feature of the complexity of the algorithm, by which it can be identified, is that after each iteration, the sample size will be reduced by about half

Code example:

JavaScript
 
function isContains(array, value) {
  let left = 0
  let right = array.length - 1

  while (left <= right) {
    const mid = Math.floor((left + right) / 2)

    if (array[mid] === value) return true
    else if (array[mid] < value) left = mid + 1
    else right = mid - 1
  }

  return false
}

const array = [1, 2, 5, 8, 100]

console.log(isContains(array, 5)) // true
console.log(isContains(array, 9)) // false

In this niche of complexity, you can find more advanced search algorithms, such as - Binary search.


O(n log n) - Linearithmic

O(n log n) - Linearithmic


This complexity is often compound, and can often, but not always, be decomposed into two nested loops, one with O(n) and O(log n) complexity. Algorithms of this type in the worst cases can degrade to the level of O(n^2).

Code example:

JavaScript
 
const matrix = [
  [1, 2, 3],
  [1, 2, 3],
  [1, 2, 3],
]
let sum = 0
for (let i = 0; i < matrix.length; i++) {
  for (j = 1; j < matrix[i].length; j *= 2) {
    sum += matrix[i][j]
  }
}

console.log(sum) // 15

In the category of such complexity, there are advanced sort algorithms, such as - Quick sort, Merge sort, etc


Conclusion

Let's summarize everything from above and put all the difficulties on one chart.

Combined chart


On a really big amount (n > billions of elements,) of data optimality scale from worst to best would look like this - O(n^2) -> O(n log n) -> O(n) -> O(log n) -> O(1).

I want to emphasize once again that these are the difficulties that are most often encountered in programming, but in fact, the classification of notations is bigger. You need to understand that one and the same task has a large number of solutions, and for evaluating and choosing the best one, this notation can be considered as one of the options. But do not forget that this is only one of the ways and far from the only one. If you write super-optimal code and arrive at a constant complexity score, but it's impossible or hard to maintain, then it's still bad code.

P.S. Useful cheat sheet for remembering time complexity and space complexity - BigoCheatSheet

Data structure

Opinions expressed by DZone contributors are their own.

Trending

  • Revolutionizing Algorithmic Trading: The Power of Reinforcement Learning
  • Operator Overloading in Java
  • Authorization: Get It Done Right, Get It Done Early
  • How to LINQ Between Java and SQL With JPAStreamer

Comments

Partner Resources

X

ABOUT US

  • About DZone
  • Send feedback
  • Careers
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • Become a Contributor
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 600 Park Offices Drive
  • Suite 300
  • Durham, NC 27709
  • support@dzone.com

Let's be friends: