סיבוכיות – הבדלי גרסאות

|-

|קבוע

|-

|לוגריתמי

|-

|לינארי

|-

|

|-

|פולינומי

|-

|מעריכי

|-

|עצרתי

|}

 

כאשר רמת הסיבוכיות של בעיה היא [[פולינום|פולינומית]] (או פחות מזה) הבעיה נחשבת כבעלת פתרון "[[חישוב יעיל|יעיל]]", משום שהגדלת אורך הקלט אינה מביאה לשינוי דרמטי בזמן הנחוץ לפתרון הבעיה. לעומת זאת, כאשר לבעיה סיבוכיות [[פונקציה מעריכית|מעריכית]] (אקספוננציאלית), שינוי קטן באורך הקלט מביא לשינוי מהותי בזמן הנחוץ לפתרון הבעיה. לדוגמה, כאשר הזמן הנחוץ לפתרונה של בעיה הוא <math>\ O(2^n)</math> (סיבוכיות מעריכית) הגדלת אורך הקלט ב-1 מביאה להכפלת הזמן הנחוץ לפתרון הבעיה.