Measuring the complexity

Contents	Notation
Measuring the complexity
Constant time	O(1)
Linear time	O(n)
Quadratic time	O(n2)
Logarithmic time	O(logn)
Exponential time	O(2^n)

Measuring the complexity

• Time and space complexity is measured using the Big-O notation.
• Sometimes we can improve time complexity by the trading off with space complexity and vice-versa.

Big-O

• This is used to measure the time complexity, meaning the performance of an algorithm.
• Using this analysis, we can determine if the program is scalable or not.
• Say, you write a program and it runs quickly on your computer does not mean it will run quickly when the size of the input grows.
• Certain operations are more or less costly depending on what data structures we use.
  • Accessing an element in an array is fast but if you want to constantly remove an element from an array or add an element to an array, it can be expensive since constantly we have to resize the array.
  • So if our task involves constantly removing and adding an element, we need to use a linkedlist But the catch here is accessing the element from a linked list is slow

Measuring the SPACE complexity

• Measuring the space complexity is a bit different, Consider the program

fun printData(inputData : IntArray){ 
    // Space Complexity = O(n)
    var newCopiedData : IntArray = inputData

    // Space Complexity = O(1)
    for(input in inputData){
      println("Data$input")
    }
}

• So while calculating the space complexity, We ignore the value that is passed as a parameter into a function, And we consider additional space allocated in the function, Based on the space allocated we calculate the complexity.

Measuring O(1) - Constant time

• Consider the snipped below where we print a value to the screen.
• Here the time complexity is O(1)

fun printData(inputData : IntArray){
        System.out.println("Data"+inputData[0])
}

• If there are two print statements, Still the time complexity is O(1)
• This is because since we use an array and we are accessing it by index, it uses a constant amount of time

fun printData(inputData : IntArray){
        System.out.println("Data"+inputData[0])
        System.out.println("Data"+inputData[1])
}

• We are just trying to get the approximate amount of time and not the exact time since the execution time differs from system to system.
• The time complexity increases constantly as the size of the input increases

Measuring O(n) - Linear time

• The time complexity increases Linearly as the size of the input increases
• Consider a for loop and in each iteration, we are printing a value. Now if the loop maximum size is 5 then there are five iterations and if the loop size is n thus there are n iterations.
• Consider there are 2 for loops in a function from a single input then, its n+n, finally the result is n
• Consider there are 2 for loops in a function and this time there are 2 inputs to functions then, its m+n, still finally the result is n

Measuring O(n2) - Quadratic time

• Consider we have a function that is having one input parameter of collection, now for this collection say we have nested loops
• Here the time complexity will be n*n= n2
• If there are three nested loops then the complexity will be n*n*n= n3

Measuring O(logn) - Logarithmic time

• When we compare logarithmic growth with linear growth, we can see that linear growth grows at the same rate, but the logarithmic growth slows down at some point.
• An algorithm that runs in logarithmic time is more efficient and scalable than an algorithm that runs in quadratic or linear time.
• Once classic example for this is the linear search and binary search comparison.
• Say there is a collection of numbers from 1 to 10. The number 10 is at the end. Now we need to find the number 10. If we use a linear search strategy maximum of 10 iterations but if we use the binary search strategy, on every iteration the collection is reduced by half meaning time to calculate the item reduces continuously, we can binary search has logarithmic time complexity.

Measuring O(2^n) - Exponential time

• This is exactly opposite to the constant time and should be avoided at all costs.