Efisiensi Algoritma dan Notasi O-Besar


  • Subandijo Subandijo Bina Nusantara University




algorithm complexity, algorithm efficiency, Brute-force algorithm, asymptotic estimation, big-O notation


Efficiency or the running time of an algorithm is usually calculated with time complexity or space complexity as a function of various inputs. It is common to estimate their complexity in the asymptotic sense, i.e., to estimate the complexity function for arbitrarily large input. Brute-force algorithm is the easiest way to calculate the performance of the algorithm. However, it is not recommended since it does not sufficiently explain the efficiency of the algorithm. Asymptotic estimaties are used because different implementations of the same algorithm may differ in efficiency. The big-O notation is used to generate the estimation.



Plum Analytics


Arora, S. and Barak, B. (2009). Computational Complexity: A Modern Approach. New York: Cambridge University Press.

Dave, P. H. and Dave, H. B. (2007). Design and Analysis of Algorithms: Efficiency of Algorithms, 371 – 404. Delhi: Pearson Education India.

Goldreich, Oded. (2008). Computational Complexity: A Conceptual Perspective. New York: Cambridge University Press.

Greene, D. A. & Knuth, D. E. (1982). Mathematics for the Analysis of Algorithms (2nd ed.). Boston: Birkhäuser.

Higham, N. J. (1998). Handbook of Writing for the Mathematical Sciences, (2nd ed.). Philadelphia: SIAM.

Knuth, D. E. (1976). Big Omicron and big Omega and big Theta. ACM SIGACT News, 8 (2).

Knuth, D. E. (1998). Teach Calculus with Big O. Notices of the American Mathematical Society, 45 (6), 687. Diakses dari http://www.ams.org/notices/199806/commentary.pdf.

Knuth, D. E. (1999). The Art of Computer Programming, (3rd ed.). Boston: Addison-Wesley.

Sedgewick, R. (1998). Algorithms in C, Parts 1-4. Fundamentals, Data Structures, Sorting, Searching, (3rd ed.). Boston: Addison-Wesley.






Abstract 672  .
PDF downloaded 1560  .