Question

In this summary, as you continue to investigate the different options to analyze algorithms, you are requested to create a PowerPoint presentation (got this covered) to explain this topic to upper management.

Your presentation should include 1 slide for each of the following:

Title page

Content

------bolded is what I need help with-----

***The answer should be written, divided into sections, please****

Big Oh overview

Big Omega overview

Big Theta overview

Empirical analyses of algorithms

Example of how to calculate Big Oh, Big Omega, and Big Theta for a simple algorithm

Recommended algorithm analysis method to be used by your company (Hardware Company- sells to building contractors)

General functionality of the problems presented using flowcharts

You should provide enough information in the speaker notes to explain the concept that is presented in the slide.

Answer 1

Big Oh overview

Big Oh is used to analyze the performance or complexity of algorithm, in simple terms the time and memory used/utilized by some problem/algorithm to reach the solution.

This basically tells the worst-case scenario of solving the problem.Worst-case scenario is analyzed based based on the number of inputs, no. of iterations required by excluding the constant factors.

Big Omega overview

This basically tells the best-case scenario of solving the problem and this is opposite of Big Oh.This tells the best way to solve the problem by saving time and memory.

Big Theta overview

This won't tell only about the best case scenario or worst case scenario because no one want's worst case, so this is tight bound which will be in between best and worst case scenario and possibly the scenario which will occur mostly.

Example of how to calculate Big Oh, Big Omega, and Big Theta for a simple algorithm

def containsZero(arr): #assume normal array of length n with no edge cases
  for num x in arr:
    if x == 0:
       return true
  return false

1. What’s the best case? Well, if the array we give it has 0 as the first value, it will take constant time: Ω (1)
2. What’s the worst case? If the array doesn’t contain 0, we will have iterated through the whole array: O(n)

Big Oh Example

Take function

f(n) = 4.n³ + 2.n² + 7.n + 4

f(n) = 4.n³ + 2.n² + 7.n + 4

Considering g(n)=n³

f(n) ⩽ 5.g(n) for all the values of n>2

Hence, the complexity of f(n) can be represented as O(g(n))O(g(n)), i.e. O(n³)

Big Omega Example

Take the same function

f(n) = 4.n³ + 2.n² + 7.n + 4

f(n) = 4.n³ + 2.n² + 7.n + 4

Considering g(n)=n³

f(n) > 4.g(n) for all the values of n>0

Hence, the complexity of f(n) can be represented as Ω(g(n)), i.e. Ω(n³)

Big Theta Example

Take the same function

f(n) = 4.n³ + 2.n² + 7.n + 4

f(n) = 4.n³ + 2.n² + 7.n + 4

Considering g(n)=n³

4.g(n) ⩽ f(n) ⩽ 5.g(n) for all the values of n

Hence, the complexity of f(n) can be represented as θ(g(n)), i.e. θ(n³)

General functionality of the problems presented using flowcharts

I am using below chart to explain

Empirical analyses of algorithms

Big Oh is the most commonly used notation. A function f(n) can be represented is the order of g(n) that is O(g(n)), if there exists a value of positive integer n as n₀ and a positive constant c such that −

f(n)⩽c.g(n)f(n)⩽c.g(n) for n>n0n>n0 in all case

Hence, function g(n) is an upper bound for function f(n), as g(n) grows faster than f(n).

Big Omega - We say that

f(n)=Ω(g(n))f(n)=Ω(g(n))

when there exists constant c that f(n)⩾c.g(n)f(n)⩾c.g(n) for all sufficiently large value of n. Here n is a positive integer. It means function g is a lower bound for function f; after a certain value of n, f will never go below g.

Big Theta - We say that

f(n)=θ(g(n))f(n)=θ(g(n))

when there exist constants c₁ and c₂ that c1.g(n)⩽f(n)⩽c2.g(n)c1.g(n)⩽f(n)⩽c2.g(n) for all sufficiently large value of n. Here n is a positive integer.

This means function g is a tight bound for function f.