{"id":551,"date":"2023-03-23T07:37:49","date_gmt":"2023-03-23T07:37:49","guid":{"rendered":"http:\/\/learnlearn.uk\/ibcs\/?page_id=551"},"modified":"2025-04-05T11:10:22","modified_gmt":"2025-04-05T11:10:22","slug":"big-o-notation","status":"publish","type":"page","link":"https:\/\/learnlearn.uk\/ibcs\/big-o-notation\/","title":{"rendered":"Big O Notation"},"content":{"rendered":"
\n

What is Big O Notation?<\/h2>\n
\n\n

What is Big O Notation?<\/h3>\n

Big O Notation is a mathematical concept used in computer science to describe the **performance or complexity** of an algorithm. It expresses **how the execution time or memory usage grows** relative to the size of the input.<\/p>\n

Big O focuses on the **worst-case scenario**, helping developers ensure algorithms will perform reliably even with large data sets.<\/p>\n

Why It Matters<\/h4>\n

Understanding Big O is crucial for writing efficient code. Here’s why:<\/p>\n

– Efficiency:<\/strong> Better algorithms lead to faster, more efficient programs.
\n– Scalability:<\/strong> Big O helps predict how code behaves with growing input sizes.
\n– Optimization:<\/strong> Identifies bottlenecks in time and space usage.
\n– Technical Interviews:<\/strong> A key topic in coding interviews and assessments.<\/p>\n\n<\/div>

Common Notations<\/h2>\n
\n\n

Common Big O Notations<\/h3>\n\n\n\n\n\n\n\n\n\n\n\n
Big O<\/th>\nName<\/th>\nExample<\/th>\n<\/tr>\n<\/thead>\n
O(1)<\/td>\nConstant Time<\/td>\nAccessing an element in an array<\/td>\n<\/tr>\n
O(log n)<\/td>\nLogarithmic Time<\/td>\nBinary search<\/td>\n<\/tr>\n
O(n)<\/td>\nLinear Time<\/td>\nLooping through an array<\/td>\n<\/tr>\n
O(n log n)<\/td>\nLinearithmic Time<\/td>\nMerge sort, quicksort<\/td>\n<\/tr>\n
O(n\u00b2)<\/td>\nQuadratic Time<\/td>\nNested loops (e.g., bubble sort)<\/td>\n<\/tr>\n
O(2\u207f)<\/td>\nExponential Time<\/td>\nRecursive algorithms (e.g., Fibonacci)<\/td>\n<\/tr>\n
O(n!)<\/td>\nFactorial Time<\/td>\nBrute-force permutations<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

 <\/p>\n\n<\/div>

Examples<\/h2>\n
\n\n

Examples<\/h3>\n
1. O(1) \u2013 Constant Time<\/strong>\r\n\r\ndef get_first_element(arr):\r\n    return arr[0]\r\n    This function returns the first element regardless of input size.<\/pre>\n
2. O(n) \u2013 Linear Time<\/strong><\/p>\n
def print_all_elements(arr):\r\n\u00a0 \u00a0 for item in arr:\r\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0print(item)<\/pre>\n
The number of operations grows linearly with the input.<\/p>\n
3. O(n\u00b2) \u2013 Quadratic Time<\/strong><\/p>\n
def print_pairs(arr):\r\n\u00a0 \u00a0 for i in arr:\r\n\u00a0 \u00a0 \u00a0 \u00a0 for j in arr:\r\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 print(i, j)<\/pre>\n
Nested loops cause the time to grow quadratically<\/p>\n\n<\/div>
Space Complexity<\/h2>\n
\n\n
Space Complexity<\/h3>\n
Big O is also used to describe **space complexity**, or how much memory an algorithm uses.
\nO(1):<\/strong> Constant space, memory usage doesn’t grow with input.<\/p>\n
O(n):<\/strong> Linear space, memory usage grows with input size (e.g., storing results in a new array).<\/p>\n
O(n\u00b2):<\/strong> Common in matrix-based algorithms or recursive calls with large depth.<\/p>\n
Efficient memory usage is just as important as fast execution in large-scale systems<\/p>\n\n<\/div>
Tips for Analyzing Code<\/h2>\n
\n\n
Tips for Analyzing Code<\/h3>\n
– Ignore constants: O(2n) simplifies to O(n)<\/p>\n
– Drop smaller terms: O(n\u00b2 + n) simplifies to O(n\u00b2)<\/p>\n
– One loop = O(n), nested loops = O(n\u00b2), triple loops = O(n\u00b3)<\/p>\n
– Recursive functions often follow patterns like T(n) = T(n\/2) + O(1)<\/p>\n
 <\/p>\n\n<\/div>
Graph<\/h2>\n
\n\n
 <\/p>\n