Journal of Computer Technology & Applications

Journal of Computer Technology & Applications Review Article

Asymptotic Notations: A Review

  1. Ramya R.K. Department of Computer Science and Engineering, Visvesvaraya Technological University, Belgaum
  2. Vinay N. Department of Computer Science and Engineering, Visvesvaraya Technological University, Belgaum
  3. Mohamed Rafi Department of Computer Science and Engineering, Visvesvaraya Technological University, Belgaum

Abstract

Asymptotic notations play a fundamental role in assessing the efficiency and performance of algorithms, particularly as input sizes grow larger. This paper delves into three key asymptotic notations: Big O, Theta, and Omega, which are essential for understanding the upper, average, and lower bounds of an algorithm’s runtime. Big O notation specifically helps in determining the worst-case scenario of an algorithm’s growth rate, providing an upper bound on time or space complexity. Theta notation, on the other hand, defines the average-case complexity by giving both upper and lower bounds, offering a more precise measurement when the best and worst cases converge. Lastly, Omega notation is used to describe the best-case scenario, setting the lower bound on the computational complexity. Through detailed analysis and examples of different algorithms, such as sorting and searching algorithms, this paper illustrates how these notations can be applied to characterize algorithm efficiency. We also explore how asymptotic notations can guide developers in optimizing computational performance and selecting the most efficient algorithm for a given problem. By understanding the implications of Big O, Theta, and Omega, we gain valuable insights into improving the scalability and resource management of complex systems, contributing to more efficient algorithm design and implementation.

Keywords

  • Asymptotic notations
  • Big O notation
  • Omega notation
  • Optimization
  • Theta notation
  • algorithm analysis
  • computational efficiency
  • computational theory

References (21)

  1. Knuth DE. The art of computer programming. Fundamentals of Algorithms. Addison Wesley Longman Publishing, Co., Inc.: Reading, USA; 1997.
  2. Cormen TH, Leiserson CE, Rivest RL, Stein C. Introduction to Algorithms. MIT Press: Cambridge, USA; 2022.
  3. Aho AV, Hopcroft JE. The Design and Analysis of Computer Algorithms. Pearson Education: India; 1974.
  4. Tarjan RE. Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics: Philadelphia, USA; 1983.
  5. Johnson DS, Garey MR. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman; 1979.
  6. Chechik S, Larkin DH, Roditty L, Schoenebeck G, Tarjan RE, Williams VV. Better Approximation Algorithms for the Graph Diameter. Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 2013:1041-1052. doi:10.1137/1.9781611973402.78
  7. Williams VV. Multiplying matrices faster than coppersmith-winograd. Proceedings of the forty-fourth annual ACM symposium on Theory of computing. 2012:887-898. doi:10.1145/2213977.2214056
  8. Brassard G, Bratley P. Fundamentals of Algorithmics. Prentice Hall, Inc.: Englewood Cliffs, USA; 1996.
  9. Skiena SS, Skiena SS. Sorting and Searching. The Algorithm Design Manual; 2008. p. 103–44.
  10. Bentley J. Programming Pearls. Addison-Wesley: Reading, USA; 1986.
  11. Aggarwal A, Vitter JS. The input/output complexity of sorting and related problems. Communications of the ACM. 1988;31(9):1116-1127. doi:10.1145/48529.48535
  12. Arora S, Barak B. Computational Complexity: A Modern Approach. Cambridge University Press: Cambridge; 2009.
  13. Mitzenmacher M, Upfal E. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge: Cambridge University Press; 1995.
  14. Dasgupta S, Papadimitriou CH, Vazirani U. Algorithms. McGraw-Hill, Inc.: New York, USA; 2006.
  15. Goldberg AV, Tarjan RE. A new approach to the maximum-flow problem. Journal of the ACM. 1988;35(4):921-940. doi:10.1145/48014.61051
  16. Blelloch GE, Fineman JT, Gibbons PB, Shun J. Internally deterministic parallel algorithms can be fast. Proceedings of the 17th ACM SIGPLAN symposium on Principles and Practice of Parallel Programming. 2012:181-192. doi:10.1145/2145816.2145840
  17. Karp RM, Luby M, Madras N. Monte-Carlo approximation algorithms for enumeration problems. Journal of Algorithms. 1989;10(3):429-448. doi:10.1016/0196-6774(89)90038-2
  18. Bera RK. Fundamental Limits to Computing. Undergraduate Lecture Notes in Physics. 2020:171-206. doi:10.1007/978-981-15-2471-4_9
  19. Soltys-Kulinicz M. Introduction to the Analysis of Algorithms, An. World Scientific; 2018.
  20. Vrenios A. Parallel Programming in C with MPI and OpenMP [Book Review]. IEEE Distributed Systems Online. 2004;5(1):7.1-7.3. doi:10.1109/mdso.2004.1270716
  21. Gupta R, Roughgarden T. Data-driven algorithm design. Communications of the ACM. 2020;63(6):87-94. doi:10.1145/3394625