Review paper on Asymptotic Notations

Year : 2024 | Volume :15 | Issue : 03 | Page : –
By

Ramya R. K.,

Vinay N.,

Mohamed Rafi,

  1. Student, Department of Computer Science and Engineering, Visvesvaraya Technological University (VTU), Belgaum, Karnataka, India
  2. Student, Department of Computer Science and Engineering, Visvesvaraya Technological University (VTU), Belgaum, Karnataka, India
  3. Professor, Department of Computer Science and Engineering, Visvesvaraya Technological University (VTU), 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 (jocta)]

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

References

  1. Aho AV, Hopcroft JE. The design and analysis of computer algorithms. Pearson Education India; 1974.
  2. Bachmann P. Zahlentheorie: Die analytische zahlentheorie. Teubner; 1894.
  3. Cormen TH, Leiserson CE, Rivest RL, Stein C. Introduction to algorithms. MIT press; 2022 Apr 5.
  4. Knuth DE. The Art of Computer Programming, volume 1 Fundamental Algorithms. Addison Wesley Longman Publishing Co., Inc.; 1997 Jun 1.
  5. Vrenios A. Parallel programming in C with MPI and OpenMP [book review]. IEEE Distributed Systems Online. 2004 Mar 8;5(1):7-1.
  6. Soltys-Kulinicz M. Introduction To The Analysis Of Algorithms, An. World Scientific; 2018 Jan 31.
  7. Gupta R, Roughgarden T. Data-driven algorithm design. Communications of the ACM. 2020 May 21;63(6):87-94.
  8. Tarjan RE. Data structures and network algorithms. Society for industrial and Applied Mathematics; 1983 Jan 1.
  9. Johnson DS, Garey MR. Computers and intractability: A guide to the theory of NP-completeness. WH Freeman; 1979.
  10. Dasgupta S, Papadimitriou CH, Vazirani U. Algorithms. McGraw-Hill, Inc.; 2006 Sep 13.
  11. Brassard G, Bratley P. Fundamentals of algorithmics. Prentice-Hall, Inc.; 1996 Jan 5.
  12. Skiena SS, Skiena SS. Sorting and searching. The Algorithm Design Manual. 2008:103-44.
  13. Bentley J. Programming Pearls Addison-Wesley. Reading, MA. 1986.
  14. Aggarwal A, Vitter JS. The input/output complexity of sorting and related problems. Communications of the ACM. 1988 Sep 1;31(9):1116-27.
  15. Arora S, Barak B. Computational complexity: a modern approach. Cambridge University Press; 2009 Apr 20.
  16. Mitzenmacher M, Upfal E. Probability and computing: randomized algorithms and probabilistic analysis. (No Title). 1995.
  17. Chechik S, Larkin DH, Roditty L, Schoenebeck G, Tarjan RE, Williams VV. Better approximation algorithms for the graph diameter. InProceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms 2014 Jan 5 (pp. 1041-1052). Society for Industrial and Applied Mathematics.
  18. Williams VV. Multiplying matrices faster than Coppersmith-Winograd. InProceedings of the forty-fourth annual ACM symposium on Theory of computing 2012 May 19 (pp. 887-898).
  19. Goldberg AV, Tarjan RE. A new approach to the maximum-flow problem. Journal of the ACM (JACM). 1988 Oct 1;35(4):921-40.
  20. Blelloch GE, Fineman JT, Gibbons PB, Shun J. Internally deterministic parallel algorithms can be fast. InProceedings of the 17th ACM SIGPLAN symposium on Principles and Practice of Parallel Programming 2012 Feb 25 (pp. 181-192).
  21. Karp RM, Luby M, Madras N. Monte-Carlo approximation algorithms for enumeration problems. Journal of algorithms. 1989 Sep 1;10(3):429-48.
Regular Issue Subscription Review Article
Volume 15
Issue 03
Received 08/08/2024
Accepted 19/09/2024
Published 07/10/2024
Views: 68

Check Our other Platform for Workshops in the field of AI, Biotechnology & Nanotechnology.
Learn more
Check Out Platform for Webinars in the field of AI, Biotech. & Nanotech.
Learn more