Skip to content
codingtube

codingtube

Coding and Programming tutorials

  • javascript
  • React
  • ES6
  • React js
  • coding
  • ffmpeg
  • java
  • programming
  • information
  • coding
  • Privacy Policy
  • Twitter trends
  • Age Calculatore
  • Codingtube Community
  • YouTube Tags Generator
  • About
  • Toggle search form

Big O Notation in data structure

Posted on December 11, 2021December 11, 2021 By christo No Comments on Big O Notation in data structure

The Big O notation, where O stands for ‘order of’, is concerned with what happens for very large values of n. For example, if a sorting algorithm performs n2 operations to sort just n elements, then that algorithm would be described as an O(n2 ) algorithm

When expressing complexity using the Big O notation, constant multipliers are ignored. So, an O(4n) algorithm is equivalent to O(n), which is how it should be written.

If f(n) and g(n) are the functions defined on a positive integer number n, then

f(n) = O(g(n))

That is, f of n is Big–O of g of n if and only if positive constants c and n exist, such that f(n)£cg(n). It means that for large amounts of data, f(n) will grow no more than a constant factor than g(n). Hence, g provides an upper bound. Note that here c is a constant which depends on the following factors:

  • the programming language used,
  • the quality of the compiler or interpreter
  • the CPU speed
  • the size of the main memory and the access time to it
  • the knowledge of the programmer, and
  • the algorithm itself, which may require simple but also time-consuming machine instructions

If f(n) ≤ cg(n), c > 0, ∀ n ≥ n0 , then f(n) = O(g(n)) and g(n) is an asymptotically tight upper bound for f(n)

Categories of Algorithms

According to the Big O notation, we have five different categories of algorithms:

  • Constant time algorithm: running time complexity given as O(1)
  • Linear time algorithm: running time complexity given as O(n)
  • Logarithmic time algorithm: running time complexity given as O(log n)
  • Polynomial time algorithm: running time complexity given as O(nk ) where k > 1
  • Exponential time algorithm: running time complexity given as O(2n )

Limitations of Big O Notation

There are certain limitations with the Big O notation of expressing the complexity of algorithms. These limitations are as follows:

  • Many algorithms are simply too hard to analyse mathematically.
  • There may not be sufficient information to calculate the behaviour of the algorithm in the average case.
  • Big O analysis only tells us how the algorithm grows with the size of the problem, not how efficient it is, as it does not consider the programming effort.
  • It ignores important constants. For example, if one algorithm takes O(n2 ) time to execute and the other takes O(100000n2 ) time to execute, then as per Big O, both algorithm have equal time complexity. In real-time systems, this may be a serious consideration
data structure Tags:Big O Notation

Post navigation

Previous Post: Algorithm Efficiency in data structure
Next Post: Omega Notation (Ω) in data structure

Related Posts

C program to find whether a string is a palindrome or not data structure
Write a program to insert a number at a given location in an array data structure
Algorithm and Efficiency of an Algorithm data structure
Tournament Trees in data structure data structure
C program traverse a linked list data structure
Complete Binary Trees data structure

Leave a Reply Cancel reply

You must be logged in to post a comment.

Recent Posts

  • Affiliate Marketing Principles
  • The Basics You Need to Know About Affiliate Marketing
  • Affiliate Marketing Options
  • All About Affiliate Marketing
  • Classification of Database Management Systems
  • Three-Tier and n-Tier Architectures
    for Web Applications
  • Two-Tier Client/Server Architectures for DBMSs
  • Basic Client/Server Architectures in DBMS
  • Centralized DBMSs Architecture in DBMS
  • Tools, Application Environments, and Communications Facilities in DBMS

Categories

  • Affiliate marketing (5)
  • Algorithm (43)
  • amp (3)
  • android (223)
  • Android App (8)
  • Android app review (4)
  • android tutorial (60)
  • Artificial intelligence (61)
  • AWS (3)
  • bitcoin (8)
  • blockchain (1)
  • c (5)
  • c language (105)
  • cloud computing (4)
  • coding (4)
  • coding app (4)
  • complex number (1)
  • Computer Graphics (66)
  • data compression (65)
  • data structure (188)
  • DBMS (44)
  • digital marketing (9)
  • distributed systems (11)
  • ffmpeg (26)
  • game (3)
  • html (6)
  • image processing (35)
  • Inequalities (1)
  • information (4)
  • java (212)
  • java network (1)
  • javascript (9)
  • kotlin (4)
  • leetcode (1)
  • math (21)
  • maven (1)
  • mysql (1)
  • Node.js (8)
  • operating system (109)
  • php (310)
  • Principle Of Mathematical Induction (1)
  • programming (6)
  • Python (4)
  • Python data structure (9)
  • React native (1)
  • React.js (22)
  • Redux (1)
  • seo (4)
  • set (12)
  • trigonometry (6)
  • vue.js (35)
  • XML (3)

sitemap

sitemap of videos

sitemap of webstories

sitemap of website

  • Affiliate marketing
  • Algorithm
  • amp
  • android
  • Android App
  • Android app review
  • android tutorial
  • Artificial intelligence
  • AWS
  • bitcoin
  • blockchain
  • c
  • c language
  • cloud computing
  • coding
  • coding app
  • complex number
  • Computer Graphics
  • data compression
  • data structure
  • DBMS
  • digital marketing
  • distributed systems
  • ffmpeg
  • game
  • html
  • image processing
  • Inequalities
  • information
  • java
  • java network
  • javascript
  • kotlin
  • leetcode
  • math
  • maven
  • mysql
  • Node.js
  • operating system
  • php
  • Principle Of Mathematical Induction
  • programming
  • Python
  • Python data structure
  • React native
  • React.js
  • Redux
  • seo
  • set
  • trigonometry
  • vue.js
  • XML
  • Blog
  • Data compression tutorial - codingpoint
  • How to change mbstring in php 5.6
  • How to diagnose out of memory killed PHP-FPM
  • Introduction to jQuery
  • Privacy
  • Affiliate marketing
  • Algorithm
  • amp
  • android
  • Android App
  • Android app review
  • android tutorial
  • Artificial intelligence
  • AWS
  • bitcoin
  • blockchain
  • c
  • c language
  • cloud computing
  • coding
  • coding app
  • complex number
  • Computer Graphics
  • data compression
  • data structure
  • DBMS
  • digital marketing
  • distributed systems
  • ffmpeg
  • game
  • html
  • image processing
  • Inequalities
  • information
  • java
  • java network
  • javascript
  • kotlin
  • leetcode
  • math
  • maven
  • mysql
  • Node.js
  • operating system
  • php
  • Principle Of Mathematical Induction
  • programming
  • Python
  • Python data structure
  • React native
  • React.js
  • Redux
  • seo
  • set
  • trigonometry
  • vue.js
  • XML
  • Blog
  • Data compression tutorial - codingpoint
  • How to change mbstring in php 5.6
  • How to diagnose out of memory killed PHP-FPM
  • Introduction to jQuery
  • Privacy

© codingtube.tech