Constant Time Complexity O(1)
The time complexity of a function (or set of statements) is considered as O(1) if it doesn’t contain a loop, recursion, and call to any other non-constant time function.
i.e. set of non-recursive and non-loop statements
In computer science, O(1) refers to constant time complexity, which means that the running time of an algorithm remains constant and does not depend on the size of the input. This means that the execution time of an O(1) algorithm will always take the same amount of time regardless of the input size. An example of an O(1) algorithm is accessing an element in an array using an index.
Example:
- swap() function has O(1) time complexity.
- A loop or recursion that runs a constant number of times is also considered O(1). For example, the following loop is O(1).
C++
// Here c is a positive constantfor (int i = 1; i <= c; i++) { // some O(1) expressions}//This code is contributed by Kshitij |
C
// Here c is a constantfor (int i = 1; i <= c; i++) { // some O(1) expressions} |
Java
// Here c is a constantfor (int i = 1; i <= c; i++) { // some O(1) expressions}// This code is contributed by Utkarsh |
C#
// Here c is a positive constantfor (int i = 1; i <= c; i++) {// This loop runs 'c' times and performs some constant-time operations in each iteration// The time complexity of the loop is O(c)// The time complexity of the loop body is O(1)// The overall time complexity of this code is O(c)// Note that the loop starts at i=1 and goes up to i=c (inclusive)// The loop variable i is incremented by 1 in each iteration// Example of an O(1) expression: int x = 1 + 2; // this takes constant time} |
Javascript
// Here c is a constantfor (var i = 1; i <= c; i++) { // some O(1) expressions} |
Python3
# Here c is a constantfor i in range(1, c+1): # some O(1) expressions # This code is contributed by Pushpesh Raj. |
How to Analyse Loops for Complexity Analysis of Algorithms
We have discussed Asymptotic Analysis, Worst, Average and Best Cases and Asymptotic Notations in previous posts. In this post, an analysis of iterative programs with simple examples is discussed.
The analysis of loops for the complexity analysis of algorithms involves finding the number of operations performed by a loop as a function of the input size. This is usually done by determining the number of iterations of the loop and the number of operations performed in each iteration.
Here are the general steps to analyze loops for complexity analysis:
Determine the number of iterations of the loop. This is usually done by analyzing the loop control variables and the loop termination condition.
Determine the number of operations performed in each iteration of the loop. This can include both arithmetic operations and data access operations, such as array accesses or memory accesses.
Express the total number of operations performed by the loop as a function of the input size. This may involve using mathematical expressions or finding a closed-form expression for the number of operations performed by the loop.
Determine the order of growth of the expression for the number of operations performed by the loop. This can be done by using techniques such as big O notation or by finding the dominant term and ignoring lower-order terms.
Contact Us