Big O notation
Big O notation
Big O notation is a mathematical notation used to describe the asymptotic behavior of functions. It is particularly useful in computer science for analyzing the time complexity and space complexity of algorithms. Big O notation provides an upper bound on the growth rate of a function, allowing for the comparison of the efficiency of different algorithms.
Definition[edit | edit source]
Big O notation is defined as follows: A function f(n) is said to be O(g(n)) if there exist positive constants c and n0 such that for all n ≥ n0, f(n) ≤ c * g(n). In this context, f(n) represents the function being analyzed, and g(n) is the comparison function.
Common Big O Notations[edit | edit source]
Several common Big O notations are frequently used to describe the performance of algorithms:
- O(1): Constant time complexity. The algorithm's performance is independent of the input size.
- O(log n): Logarithmic time complexity. The algorithm's performance grows logarithmically with the input size.
- O(n): Linear time complexity. The algorithm's performance grows linearly with the input size.
- O(n log n): Linearithmic time complexity. The algorithm's performance grows in proportion to n log n.
- O(n^2): Quadratic time complexity. The algorithm's performance grows quadratically with the input size.
- O(2^n): Exponential time complexity. The algorithm's performance grows exponentially with the input size.
- O(n!): Factorial time complexity. The algorithm's performance grows factorially with the input size.
Usage in Computer Science[edit | edit source]
Big O notation is widely used in algorithm analysis to classify algorithms according to their performance and resource usage. It helps in understanding the scalability of algorithms and in making informed decisions about which algorithm to use in a given context.
Related Concepts[edit | edit source]
- Little o notation
- Big Theta notation
- Big Omega notation
- Time complexity
- Space complexity
- Algorithm
- Asymptotic analysis
See Also[edit | edit source]
References[edit | edit source]
External Links[edit | edit source]
 | This mathematics-related article is a stub. You can help WikiMD by expanding it. |
Search WikiMD
Ad.Tired of being Overweight? Try W8MD's physician weight loss program.
Semaglutide (Ozempic / Wegovy and Tirzepatide (Mounjaro / Zepbound) available.
Advertise on WikiMD
|
WikiMD's Wellness Encyclopedia |
| Let Food Be Thy Medicine Medicine Thy Food - Hippocrates |
Translate this page: - East Asian
中文,
日本,
한국어,
South Asian
हिन्दी,
தமிழ்,
తెలుగు,
Urdu,
ಕನ್ನಡ,
Southeast Asian
Indonesian,
Vietnamese,
Thai,
မြန်မာဘာသာ,
বাংলা
European
español,
Deutsch,
français,
Greek,
português do Brasil,
polski,
română,
русский,
Nederlands,
norsk,
svenska,
suomi,
Italian
Middle Eastern & African
عربى,
Turkish,
Persian,
Hebrew,
Afrikaans,
isiZulu,
Kiswahili,
Other
Bulgarian,
Hungarian,
Czech,
Swedish,
മലയാളം,
मराठी,
ਪੰਜਾਬੀ,
ગુજરાતી,
Portuguese,
Ukrainian
Medical Disclaimer: WikiMD is not a substitute for professional medical advice. The information on WikiMD is provided as an information resource only, may be incorrect, outdated or misleading, and is not to be used or relied on for any diagnostic or treatment purposes. Please consult your health care provider before making any healthcare decisions or for guidance about a specific medical condition. WikiMD expressly disclaims responsibility, and shall have no liability, for any damages, loss, injury, or liability whatsoever suffered as a result of your reliance on the information contained in this site. By visiting this site you agree to the foregoing terms and conditions, which may from time to time be changed or supplemented by WikiMD. If you do not agree to the foregoing terms and conditions, you should not enter or use this site. See full disclaimer.
Credits:Most images are courtesy of Wikimedia commons, and templates Wikipedia, licensed under CC BY SA or similar.
Contributors: Prab R. Tumpati, MD
