Flat Preloader Icon

Time Complexity


  • Basics of function
  • Measuring Algorithm Performance
  • Why analysis is required
  • Types of algorithm analysis
  • Time complexity
  • Asymptotic Analysis
  • Asymptotic Notations
  • Calculation Big 0 notation

Basic Of Functions

T = f(n) [ y = f(x) ]

Measuring Performance Of Algorithms

Algorithm analysis is an important part of computational complexity theory, which provides theoretical estimate’mfor the required resources of an algorithm to solve a specific computational problem

It is the determination of the amount of time and space resources required to execute it .

Why Analysis Is Required?

  • Predicting behavior of an algorithm without implementing
  • Analysis is only approximation
  • There are many influencing factors It helps us in determining the best algorithm to solve a programming problem.
  • Types of Algorithm Analysis

    1) Best case
    2) Worst case
    3) Average case
  • Certain input takes less time for an algorithm to accomplish its task .This is best case
  • Certain input takes Max time for an algorithm to accomplish its task .This is worst case
  • All other cases /total no.of cases = Average case
  • Time Complexity

    It is a measure of rate of change in time with respect to change in input size

    Various asymptotic notations are there to represent time complexity of an algorithm.

    Asymptotic Analysis

    we donot calculate the actual time taken by the algorithm to solve the problem, rather we are interested in how the time taken by an algorithm increases with the input size

    Asymptotic Notation

    1) Big O Notation
    provides an upper bound on the growth rate of time . It represent the worst case scenario

    2) Omega Notation
    provides a lower bound on the growth rate of time. It represents the best case scenario

    3) Theta Notation
    provides both an upperbound and lowerbound on the growth rate of time. It represents the average case scenario .
    c1 * g(n) <= f(n) <= c2 * g(n) here, c1 and c2 are positive constant for all n >= n0

    if g(n) = 3n3 + 5n2 + 4
    g(n) = n3
    for some no such that n>=n0

    Big O Notation

    O <= f(n) <= g(n)

    for all n >= n0

    Omega Notation

    c * g(n) <= f(n)

    for all n >= n0

    Calculate O(n)

    1) Factorial
    2) Insertion Sort

    for i=1 to n
    for(i=1 to n)
    for(j=i-1 to 0)
    o(1) o(log n) o(n) o(n logn)
    o(n2) o(n2log n) o(n3)