ScaleFree

DS & A (Algorithm Analysis - Measures of Algorithm Complexity)

| Measures of Algorithm Complexity - CHAPTER 7 |

In Chapter 4 we learned about the growth rate of an algorithm. So, as of now we already know what growth rate of an algorithm is. And In this chapter, we will discuss the different measures of algorithm growth rate/Algorithm complexity. The different measures for algorithm growth rate are:
  • Big Oh (O)
  • Big Omega (Ω)
  • Big Theta (ϴ)
Before we dive in and start discussing Big Oh, Big Omega and Big Theta I would like to introduce the concept of Upper Bound  & Lower Bound

So, What are Upper Bound and Lower Bound of an algorithm?

In simple terms, Upper bound of an algorithm is the highest growth rate that an algorithm can have. So, the algorithm cannot perform any worse than that.

Similarly, Lower bound of an algorithm is the lowest growth rate that an algorithm can have. And the algorithm cannot perform any better than that.

CAUTION : 

Upper Bound is not the Worst Case and Lower Bound is not the Best Case of an algorithm!!! It is because we are measuring the resource (such as time) required for some particular class of inputs,i.e. the Best, the Worst or the Average class of inputs. So, an algorithm might have different Upper bound and Lower bound for each of these input classes. Also, In real life application, an algorithm's growth rate usually fluctuates among the values from upper bound to the lower bound.

So, for an algorithm with best, average and worst case the definition of Upper bound & Lower bound can be written as follows,

Upper bound of an algorithm is the highest growth rate that an algorithm can have, given that the measurement is made only for some particular case of inputs namely worst-, average- or best-case inputs. And In the same way, the Lower bound can be defined as well.

Note : If the Upper Bound of an algorithm's growth rate is f(n), then we say that the algorithm is in the set of O(n) and If the Lower Bound of an algorithm's growth rate is f(n), then we say that the algorithm is in the set of Ω(n).

Case 1: Big Oh (O)
If the Upper Bound of an algorithm's growth rate, for a particular case(say, for the worst case), is f(n) while T(n) being the running time of the algorithm, then T(n) will be in the set of O(f(n)) if there exist two positive constants c and n' such that T(n) ≤ cf(n) for all n > n'
Case 2: Big Omega (Ω)
If the Lower Bound of an algorithm's growth rate for a particular case(say, for the worst case) is g(n) while T(n) being the running time of the algorithm, then T(n) will be in the set of Ω(g(n)) if there exist two positive constants c and n' such that T(n) ≥ cg(n) for all n > n'
Case 3: Big Theta (ϴ) 
If the Lower Bound and Upper bound of an algorithm's growth rate are equivalent or same, for a particular case(say, the worst case), then the algorithm is said to be in the set of ϴ(h(n)). So, if an algorithm is in ϴ(h(n)) then it is in the set of O(n) and Ω(n) as well.



Points to Remember
  • If f(n) is in O(g(n)) and g(n) is in O (h(n)), then f(n) is in O(h(n))
  • If f(n) is in O(kg(n)) where k > 0 then f(n) is in O (g(n))
  • If f(n) is in O(g (n)) and f'(n) is in O(g'(n)), then f(n) + f'(n) is in O(max(g(n),g'(n))) 
  • If f(n) is in O(g (n)) and f'(n) is in O(g'(n)), then f(n)f'(n) is in O(max(g(n)g'(n)))
Similar, rules are valid for Big Omega (Ω) as well.

( If you like the contents here, follow TSP on social media to get notified on future updates)



Comments

Share on Social Media

Most Viewed Posts

DS & A (Lists - Array Based)

SPACE & DRAGONS

DATA STRUCTURES AND ALGORITHMS