l2t

What is Big O Notation?

How to find space/time complexity of a program?

What is Big O Notation?

Big.O Notation is used to find/calculate time/space complexity of a problem. It help us write better and efficient code.

Why do we care time and space complexity:

  • when you write a code it matters how long a specific problem takes to execute
  • we care about two things most
    • space (memory)
    • time (how long it takes to execute)

If you are a developer and given task to write some programs, if your programs takes to long to run and you are not efficiently using memory it will impact your customer and your app performance.

You do not need to learn in depth but atleast you know some basics of big o it will help you identify loop holes in your code and make you a better programmer.

How does Big O Helps saves developers?

Every program we write has two types of complexity attached to it space and time:

  • with larger input size it effects how we use memory(space) and time (how long it takes to execute your program)
  • By learning big O notation it helps us find bottlenecks in our program and imrpove our code to speed up our program
  • If we know about different types of complexities and how to cure them we can improve
    • time/space complexity of our program
    • find right solution to implement in our program

What is time/space complexity?

Computer requires memory to perform different calulations. When given program takes longer to output something it does affect overall response time. When a program takes lot more memory then it actually requires there are chances of crashing your program.

Time complexity means overall time it takes to execute your entire program.

Space complexity means amount of memory it needs in order to execute certain program.

How to calculate time complexity of a program?

Let's consider following code:

function sum($a, $b) {
    return $a + $b;  // statement
}

Consider every single statement in your program as 1 unit of time. A program can have following types of statements:

  • static - those who do not depend on input size
  • dynamic - those who depends on input size

Overall time complexity is sum of static and dynamic statements unit of time.

What is dynamic statment? How do we calulate sum of time unit for dynamic statements:

  • Those statements that depends on input size are considered as dynamic statements
  • To calculate sum of time units for dynamic statements:
    • you should consider number of repetations it makes multiply with statments inside each repetations
    • Loops are considered as dynamic statements if they depends on input size
      • Loops are considered as single statements and whatever we write inside loop is considered as static statements
      • If loop takes 1 repetation and it has 4 static statements inside them it will be 1*4 = 4 unit of time
  • This would help us estimate how long a program roughly takes to execute entire program
  • To find overall complexity consider following:
    • ignore constants
    • consider only higher term from the equation

Calculate Time Complexity of following program:

// following function has all static statements
// because it does not depend on any input size.
function sum() {
    $a = 1;          // statement-1
    $b = 2;          // statement-2   
    return $a + $b;  // statement-3
}

// Overall compexity of the program
// Big(O) = 1 + 1 + 1  = 1 (we only consider higher term from the equation)

// each static statement is considered as 1 unit of time
// we have three static statements to calulate overall compexity 
// we only consider higher term which is 1 unit in our case to calulate time complexity
// we can not say time compexity is 3 unit of time.

How to calculate space complexity of a program?

When we write program we wont know followings:

  • how variable/functions stack allocate memory
  • to calculate space complexity
    • consider scalar variables as 1 unit of space
    • dynamic variables that depends on input will be calculated differertly
  • What things affect space complexity:
    • variables declaration and assignments
    • return statements
    • call stacks etc...
  • To find overall complexity consider following:
    • ignore constants
    • consider only higher term from the equation

Calculate Space Complexity of following program:

// following function has all static statements
// because it does not depend on any input size.
function sum() {
    $a = 1;          // statement-1 ( 2 unit of space)
    $b = 2;          // statement-2 ( 2 unit of space) 
    return $a + $b;  // statement-3 ( 1 unit of space)
}

// To calculate overall space complexity we would have to
// look at each statement and see if it takes any space unit
// i.e. $a = 1 this statement has two operations 1) declaration 2) assignment
// therefore it takes 2 unit of space

// Overall Space Complexity would be
// Big (O) = 2 + 2 + 1 = 2 (we only consider higher term from the equation)

I hope with this simple formula atleast we would be able to write different equations for given program and we would take higher term from the equation and define it as our overall complexity.

I know it is bit difficult to grasp the concept in the beginning but as we move on with more examples you would have clear understanding on how we can efficiently calculate time/space complexity of any given program.

What are the different types of Big O complexities?

Followings are some of the different types of complexities:

  • Constant Time: O(1)
  • Logarithmic Time: O(log n)
  • Linear Time: O(n)
  • Linearithmic Time: O(n log n)
  • Quadric Time: O(n^2)
  • Cubic TIme: O(n^3)
  • Plynomial TIme: O(n^k)
  • Exponential Time: O(b^n)
  • Factorial Time: O(n!)

n - size of input, complexities are order in from smallest to largest.

Reference: https://danielmiessler.com/study/big-o-notation

In upcoming blogs we would learn how to practically find each complexity and how to calculate overall complexity of any program. How to solve big problems in simple and efficient manner.

Next, we will learn about complexity of loops and do lot more practise.

Complexity of for Loops