Asymptotic Notations: A Review

Year : 2024 | Volume : 15 | Issue : 03 | Page : 17 33
    By

    Ramya R.K.,

  • Vinay N.,

  • Mohamed Rafi,

  1. Student, Department of Computer Science and Engineering, Visvesvaraya Technological University, Belgaum, Karnataka, India
  2. Student, Department of Computer Science and Engineering, Visvesvaraya Technological University, Belgaum, Karnataka, India
  3. Professor, Department of Computer Science and Engineering, Visvesvaraya Technological University, Belgaum, Karnataka, India

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, Theta notation, Omega notation, algorithm analysis, computational efficiency, optimization, computational theory

[This article belongs to Journal of Computer Technology & Applications ]

How to cite this article:
Ramya R.K., Vinay N., Mohamed Rafi. Asymptotic Notations: A Review. Journal of Computer Technology & Applications. 2024; 15(03):17-33.
How to cite this URL:
Ramya R.K., Vinay N., Mohamed Rafi. Asymptotic Notations: A Review. Journal of Computer Technology & Applications. 2024; 15(03):17-33. Available from: https://journals.stmjournals.com/jocta/article=2024/view=177276


References

  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. In: Proceedings of the Twenty-Fifth Annual ACM-Siam Symposium on Discrete Algorithms 2014 Jan 5. Society for Industrial and Applied Mathematics: Philadelphia, USA; 2014. p. 1041–52. DOI: 10.1137/1.9781611973402.78.
  7. Williams VV. Multiplying matrices faster than Coppersmith-Winograd. In: Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing 2012 May 19. 2012. p. 887–98. 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. Commun ACM. 1988;31:1116–27. 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. J ACM. 1988;35:921–40. DOI: 10.1145/48014.61051.
  16. Blelloch GE, Fineman JT, Gibbons PB, Shun J. Internally deterministic parallel algorithms can be fast. In: Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming; 2012 Feb 25; New Orleans, Louisiana, USA. New York, NY: Association for Computing Machinery; 2012. p. 181–92. DOI: 10.1145/2145816.2145840.
  17. Karp RM, Luby M, Madras N. Monte-Carlo approximation algorithms for enumeration problems. J Algorithms. 1989;10:429–48. DOI: 10.1016/0196-6774(89)90038-2.
  18. Bera RK. Fundamental limits to computing. In: Bera RK, editor. The Amazing World of Quantum Computing. Undergraduate Lecture Notes in Physics. Singapore: Springer; 2020. pp 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:7.1–7.3. DOI: 10.1109/MDSO.2004.1270716.
  21. Gupta R, Roughgarden T. Data-driven algorithm design. Commun ACM. 2020;63:87–94. DOI: 10.1145/3394625.
Regular Issue Subscription Review Article
Volume 15
Issue 03
Received 08/08/2024
Accepted 19/09/2024
Published 07/10/2024
376


My IP

PlumX Metrics