l2t

Big O Constant Time

What is constant time complexity?

What is constant time complexity?

When an algorithm or a program takes constant time to run or execute the entire program it has constant time complexity. No matter how many times you run this program it will take roughly same amount of time every time you run it.

Big O constant time O(1) do not depend on any inpur size. Following(s) are some of the examples of constant time statements:

  • declaring variables
  • variable assignments
  • printing or echoing any text
  • return statements

Let's take following example to understand:

function sum() {
  return 1+1; // static statement (1 unit of time)
}

If you look at above code no matter how many time you run on and average it would roughly take same amount of time. It does not depend on any input size.

If you assign 1 unit of time to static statement you can say that above program has O(1) complexity. To calculate overall time/space complexity of any program you have to consider following things:

  • sum of all statements
  • ignore all constants
  • consider the bigger term from the equation

What is the time/space complexity of following program?

function sum() {
   $a = 1;           // 1 unit of space/time (static statement)
   $b = 2;           // 1 unit of space/time (static statement)
   return $a + $b;   // 1 unit of space/time (static statement)
}

To calculate time/space complexity of above program:

  • we have to assign 1 unit of time/space to all static statements.
  • sum of all static statements
  • pick the bigger term from the equation
function sum() {
   $a = 1;           // 1 unit of space/time (static statement)
   $b = 2;           // 1 unit of space/time (static statement)
   return $a + $b;   // 1 unit of space/time (static statement)
}

Big(O) = 1 + 1 + 1
       = O(1) -> considering 1 as higest term from our equation

If you analysis above code with depth knowledge equation might look differernt however it would end up with same complexity overall. Therefore above method works well to figure out complexity of any program.

Hope this tutorial helps you learn in depth about constant time complexity and how you can calculate it with simple method. Please share and support my articles if you like them so that I can write more good articles. Thank you.