Refers to the time/space complexity of an algorithm in the worst case scenario. Some algorithms have different complexity analysis depending on the scenario. For example, best case, average case and worst case scenario based on how sorted the input is. Usually worst case scenario is the focus.
| Name | Big oh |
| ----------- | ---------- |
| Constant | O(1) |
| Logarithmic | O(log(n)) |
| Linear | O(n) |
| Log-linear | O(nlog(n)) |
| Quadratic | O(n^2) |
| Cubic | O(n^3) |
| Exponential | O(2^n) |
| Factorial | O(n!) |
O(1) - Constant
|
|
|
|
|
|/----------------\
void *hash_get(Hash *hash, int key) {
return hash->buckets[hash_code(hash, key)];
}
1.00 ┼───────────────────────────────────────────────────────────────────────
Constant 𝚯(1)
O(log(n)) - Logarithmic
|
|
|
|
| _-----------____
|/
RBTree *rb_tree_find(RBTree *t, int value) {
if (!t)
return NULL;
int x = compare(value, t->value);
return x == 0 ? t : rb_tree_find(x < 0 ? t->left : t->right, value);
}
6.64 ┼ ╭────
6.44 ┤ ╭────────╯
6.23 ┤ ╭───────╯
6.02 ┤ ╭──────╯
5.81 ┤ ╭─────╯
5.61 ┤ ╭────╯
5.40 ┤ ╭───╯
5.19 ┤ ╭───╯
4.98 ┤ ╭──╯
4.78 ┤ ╭──╯
4.57 ┤ ╭─╯
4.36 ┤ ╭──╯
4.15 ┤ ╭╯
3.94 ┤ ╭─╯
3.74 ┤ ╭╯
3.53 ┤ ╭─╯
3.32 ┤ ╭╯
3.11 ┤ │
2.91 ┤ ╭╯
2.70 ┤ ╭╯
2.49 ┤ │
2.28 ┤ ╭╯
2.08 ┤ │
1.87 ┤ ╭╯
1.66 ┤ │
1.45 ┤ │
1.25 ┤╭╯
1.04 ┤│
0.83 ┤│
0.62 ┤│
0.42 ┤│
0.21 ┤│
0.00 ┼╯
Logarithmic 𝚯(logn)
O(n) - Linear
| /
| /
| /
| /
| /
|/
bool find(int n, int items[n], int value) {
for (int i = 0; i < n; i++) {
if (items[i] == value)
return true;
}
return false;
}
100.00 ┼ ╭─
96.91 ┤ ╭──╯
93.81 ┤ ╭─╯
90.72 ┤ ╭─╯
87.62 ┤ ╭─╯
84.53 ┤ ╭─╯
81.44 ┤ ╭──╯
78.34 ┤ ╭─╯
75.25 ┤ ╭─╯
72.16 ┤ ╭─╯
69.06 ┤ ╭──╯
65.97 ┤ ╭─╯
62.88 ┤ ╭─╯
59.78 ┤ ╭─╯
56.69 ┤ ╭─╯
53.59 ┤ ╭──╯
50.50 ┤ ╭─╯
47.41 ┤ ╭─╯
44.31 ┤ ╭─╯
41.22 ┤ ╭─╯
38.12 ┤ ╭──╯
35.03 ┤ ╭─╯
31.94 ┤ ╭─╯
28.84 ┤ ╭─╯
25.75 ┤ ╭──╯
22.66 ┤ ╭─╯
19.56 ┤ ╭─╯
16.47 ┤ ╭─╯
13.38 ┤ ╭─╯
10.28 ┤ ╭──╯
7.19 ┤ ╭─╯
4.09 ┤╭─╯
1.00 ┼╯
Linear 𝚯(n)
O(nlog(n)) - Log-linear
| /
| /
| /
| /
| /
|/
static void quick_sort(int *items, int min, int max) {
if (min >= max)
return;
int index = partition(items, min, max);
quick_sort(items, min, index - 1);
quick_sort(items, index + 1, max);
}
664 ┼ ╭
644 ┤ ╭─╯
623 ┤ ╭─╯
602 ┤ ╭─╯
581 ┤ ╭─╯
561 ┤ ╭─╯
540 ┤ ╭─╯
519 ┤ ╭─╯
498 ┤ ╭╯
478 ┤ ╭─╯
457 ┤ ╭─╯
436 ┤ ╭─╯
415 ┤ ╭─╯
394 ┤ ╭─╯
374 ┤ ╭─╯
353 ┤ ╭─╯
332 ┤ ╭─╯
311 ┤ ╭─╯
291 ┤ ╭──╯
270 ┤ ╭─╯
249 ┤ ╭─╯
228 ┤ ╭─╯
208 ┤ ╭─╯
187 ┤ ╭─╯
166 ┤ ╭──╯
145 ┤ ╭─╯
125 ┤ ╭──╯
104 ┤ ╭─╯
83 ┤ ╭──╯
62 ┤ ╭─╯
42 ┤ ╭──╯
21 ┤ ╭───╯
0 ┼──╯
𝚯(n logn)
O(n^2), O(n^3), O(n^4) - Polynomial
| |
| |
| /
| )
| /
|/
void f(int n) {
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
printf("%d %d\n", i, j);
}
}
}
10000 ┼ ╭
9688 ┤ ╭╯
9375 ┤ ╭╯
9063 ┤ ╭─╯
8750 ┤ ╭╯
8438 ┤ ╭╯
8125 ┤ ╭╯
7813 ┤ ╭╯
7500 ┤ ╭─╯
7188 ┤ ╭╯
6875 ┤ ╭╯
6563 ┤ ╭─╯
6250 ┤ ╭╯
5938 ┤ ╭─╯
5625 ┤ ╭╯
5313 ┤ ╭─╯
5000 ┤ ╭╯
4688 ┤ ╭─╯
4376 ┤ ╭─╯
4063 ┤ ╭╯
3751 ┤ ╭─╯
3438 ┤ ╭─╯
3126 ┤ ╭─╯
2813 ┤ ╭─╯
2501 ┤ ╭──╯
2188 ┤ ╭─╯
1876 ┤ ╭─╯
1563 ┤ ╭──╯
1251 ┤ ╭───╯
938 ┤ ╭──╯
626 ┤ ╭────╯
313 ┤ ╭─────╯
1 ┼────────╯
Polynomial 𝚯(n^2)
O(2^n) - Exponential
E.g. 2 * 2 * 2 * 2 … (n times)
| |
| |
| |
| |
| |
|/
int f(int n) {
if (n <= 1) return n;
return f(n -2) + f(n -1);
}
1267650600228229401496703205376 ┼ ╭
1228036518971097232699931230208 ┤ │
1188422437713965063903159255040 ┤ │
1148808356456832895106387279872 ┤ │
1109194275199700726309615304704 ┤ │
1069580193942568557512843329536 ┤ │
1029966112685436388716071354368 ┤ │
990352031428304219919299379200 ┤ │
950737950171172051122527404032 ┤ │
911123868914039882325755428864 ┤ │
871509787656907713528983453696 ┤ │
831895706399775544732211478528 ┤ │
792281625142643375935439503360 ┤ │
752667543885511207138667528192 ┤ │
713053462628379038341895553024 ┤ │
673439381371246869545123577856 ┤ │
633825300114114700748351602688 ┤ │
594211218856982531951579627520 ┤ │
554597137599850363154807652352 ┤ │
514983056342718194358035677184 ┤ ╭╯
475368975085586025561263702016 ┤ │
435754893828453856764491726848 ┤ │
396140812571321687967719751680 ┤ │
356526731314189519170947776512 ┤ │
316912650057057350374175801344 ┤ │
277298568799925181577403826176 ┤ │
237684487542793012780631851008 ┤ │
198070406285660843983859875840 ┤ ╭╯
158456325028528675187087900672 ┤ │
118842243771396506390315925504 ┤ │
79228162514264337593543950336 ┤ ╭╯
39614081257132168796771975168 ┤ ╭╯
0 ┼──────────────────────────────────────────────────────────────────╯
Exponential 𝚯(2^n)
O(n!) - Factorial
E.g.
n * (n-1) * (n-2) …
||
||
||
||
||
|/
int f(int n) {
if (n < 1) return 1;
return n * f(n - 1);
}
93326215443944150965646704795953882578400970373184098831012889540582227238570431295066113089288327277825849664006524270554535976289719382852181865895959724032 ┼ ╭
90409771211320894723678960937099742018530417689077610513736049894308587881917371125019252709659385351025577475535631344215463015406338066470094307934227922944 ┤ │
87493326978697638481711217078245601458659865004971122196459210248034948525264310954972392330030443424225305287064738417876390054522956750088006749972496121856 ┤ │
84576882746074382239743473219391460898789312320864633879182370601761309168611250784925531950401501497425033098593845491537317093639575433705919192010764320768 ┤ │
81660438513451125997775729360537320338918759636758145561905530955487669811958190614878671570772559570624760910122952565198244132756194117323831634049032519680 ┤ │
78743994280827881950138260173527833613412385832207539075090186094257588498887003981440165955853071238770203813417571981933120864867433486285399073307165196288 ┤ │
75827550048204625708170516314673693053541833148101050757813346447983949142233943811393305576224129311969931624946679055594047903984052169903311515345433395200 ┤ │
72911105815581369466202772455819552493671280463994562440536506801710309785580883641346445196595187385169659436475786129254974943100670853521223957383701594112 ┤ │
69994661582958113224235028596965411933800727779888074123259667155436670428927823471299584816966245458369387248004893202915901982217289537139136399421969793024 ┤ │
67078217350334856982267284738111271373930175095781585805982827509163031072274763301252724437337303531569115059534000276576829021333908220757048841460237991936 ┤ │
64161773117711600740299540879257130814059622411675097488705987862889391715621703131205864057708361604768842871063107350237756060450526904374961283498506190848 ┤ │
61245328885088344498331797020402990254189069727568609171429148216615752358968642961159003678079419677968570682592214423898683099567145587992873725536774389760 ┤ │
58328884652465100450694327833393503528682695923018002684613803355385671045897456327720498063159931346114013585886833840633559831678384956954441164794907066368 ┤ │
55412440419841832014396309302694709134447964359355632536875468924068473645662522621065282918821535824368026305650428571220537177800382955228698609613310787584 ┤ │
52495996187218587966758840115685222408941590554805026050060124062838392332591335987626777303902047492513469208945047987955413909911622324190266048871443464192 ┤ │
49579551954595331724791096256831081849071037870698537732783284416564752975938275817579916924273105565713197020474155061616340949028241007808178490909711663104 ┤ │
46663107721972075482823352397976941289200485186592049415506444770291113619285215647533056544644163638912924832003262135277267988144859691426090932947979862016 ┤ │
43746663489348819240855608539122800729329932502485561098229605124017474262632155477486196165015221712112652643532369208938195027261478375044003374986248060928 ┤ │
40830219256725562998887864680268660169459379818379072780952765477743834905979095307439335785386279785312380455061476282599122066378097058661915817024516259840 ┤ │
37913775024102306756920120821414519609588827134272584463675925831470195549326035137392475405757337858512108266590583356260049105494715742279828259062784458752 ┤ │
34997330791479050514952376962560379049718274450166096146399086185196556192672974967345615026128395931711836078119690429920976144611334425897740701101052657664 ┤ │
32080886558855806467314907775550892324211900645615489659583741323966474879601788333907109411208907599857278981414309846655852876722573794859308140359185334272 ┤ │
29164442326232550225347163916696751764341347961509001342306901677692835522948728163860249031579965673057006792943416920316779915839192478477220582397453533184 ┤ │
26247998093609293983379420057842611204470795277402513025030062031419196166295667993813388651951023746256734604472523993977706954955811162095133024435721732096 ┤ │
23331553860986037741411676198988470644600242593296024707753222385145556809642607823766528272322081819456462416001631067638633994072429845713045466473989931008 ┤ │
20415109628362781499443932340134330084729689909189536390476382738871917452989547653719667892693139892656190227530738141299561033189048529330957908512258129920 ┤ │
17498665395739525257476188481280189524859137225083048073199543092598278096336487483672807513064197965855918039059845214960488072305667212948870350550526328832 ┤ │
14582221163116269015508444622426048964988584540976559755922703446324638739683427313625947133435256039055645850588952288621415111422285896566782792588794527744 ┤ │
11665776930493024967870975435416562239482210736425953269107358585094557426612240680187441518515767707201088753883571705356291843533525265528350231846927204352 ┤ │
8749332697869768725903231576562421679611658052319464951830518938820918069959180510140581138886825780400816565412678779017218882650143949146262673885195403264 ┤ │
5832888465246512483935487717708281119741105368212976634553679292547278713306120340093720759257883853600544376941785852678145921766762632764175115923463602176 ┤ │
2916444232623256241967743858854140559870552684106488317276839646273639356653060170046860379628941926800272188470892926339072960883381316382087557961731801088 ┤ │
0 ┼──────────────────────────────────────────────────────────────────────╯
Factorial 𝚯(n!)