Un algoritm este liniar daca are complexitatea in timp polinomiala. Exemple:
[tex]BubbleSort \rightarrow\ O(n^2)\\LinearSearch \rightarrow O(n)\\ InsertionSort \rightarrow O(n^2)[/tex]
[tex]BackTracking \rightarrow O(n^k)|_{k=dimensiunea\ spatiului\ solutiilor}[/tex]
Un algoritm este neliniar (se poate numi ramificat) daca are complexitatea in timp nonpolinomiala. Exemple:
[tex]BinarySearch \rightarrow O(\log_2n)\\MergeSort \rightarrow O(n\cdot\log_2n)\\HeapSort \rightarrow O(n\cdot \log_2n)\\[/tex]
Algoritmii neliniari (ramificati) sunt uzual implementati prin functii recursive. Algoritmii liniari sunt uzual implementati prin bucle (for, while, do-while).
