Movatterモバイル変換


[0]ホーム

URL:


Skip to content
DEV Community
Log in Create account

DEV Community

Cover image for Do you know the Big-O notation?
Codacy profile imageHeloisa Moraes
Heloisa Moraes forCodacy

Posted on

     

Do you know the Big-O notation?

This article is being shared from the Codacy Code Quality Community, and was written by one of our members. Check out the original posthere and feel free to join the community.

If you had an algorithm-related course as I did, you’ve probably heard of the term Big-O notation. It’s one of the most fundamental tools to analyze the cost of an algorithm before implementing it.

Big-O notation describes the complexity of your code using algebraic terms, but let’s take a simpler approach today when analyzing five typical Big-Os.

O(1) - constant complexity

No matter the input data set size, it will always take constant time (or space) to execute.

int constantExample(int x, int y) {     return x + y;}
Enter fullscreen modeExit fullscreen mode

O(log(n)) - logarithmic complexity

Generally reduces the problem size with each iteration.

int logarithmicExample(int n) {     while (n > 1) {          n = n / 2;     }}
Enter fullscreen modeExit fullscreen mode

O(n) - linear complexity

It increases linearly and in direct proportion to the size of the input.

boolean linearExample(IList elements, int value) {     foreach (var element in elements) {          if (element == value) return true;     }     return false;}
Enter fullscreen modeExit fullscreen mode

O(n2) - quadratic complexity

It’s directly proportional to the square of the size of the input.

void quadraticExample(int array[], int size) {     for (int i = 0; i < size; i++) {          for (int j = 0; j < size; j++) {               print(array[i], array[j]);          }     }}
Enter fullscreen modeExit fullscreen mode

O(2n) - exponential complexity

Its growth doubles with each addition to the input data set. A great example is the Fibonacci recursive function.

int fibonacci(int number) {     if (number <= 1) return number;     return fibonacci(number - 1) + fibonacci(number - 2);}
Enter fullscreen modeExit fullscreen mode

💡 Do you want a Big-O cheatsheet?Head over here! You’ll find complexities for data structures and algorithms in the best, average, and worst-case scenarios.

Big-O complexity chart from Big-O Cheat Sheet

Top comments(0)

Subscribe
pic
Create template

Templates let you quickly answer FAQs or store snippets for re-use.

Dismiss

Are you sure you want to hide this comment? It will become hidden in your post, but will still be visible via the comment'spermalink.

For further actions, you may consider blocking this person and/orreporting abuse

More fromCodacy

DEV Community

We're a place where coders share, stay up-to-date and grow their careers.

Log in Create account

[8]ページ先頭

©2009-2025 Movatter.jp