Chapter 7

Question 1

Does f(n)En(square)

Answer 1

Yes

Question 2

What is definition of O notation and omega notation

Answer 2

The definition of Omega notation relies on proving both a lower and upper asymptotic bound

Question 3

What is O notation

Answer 3

The O-notation is used to state only the asymptotic upper bounds

Question 4

What is omega notation

Answer 4

The omega notation allows us to state only the asymptotic lower bound

Question 5

What are Asymptotic Notations

Answer 5

Asymptotic Notations are languages that allow us to analyze an algorithm’s running time by identifying its behavior as the input size for the algorithm increases.

Question 6

How to make an algorithm

Answer 6

First make mathematical definition of a problem, then make a strategy, and then find an algorithm. Then write algorithm in suedo language and then write analysis on it.

Question 7

What is divide and conquer strategy

Answer 7

The divide and conquer is a strategy to solve a large number of computational problems. It has 3 parts.
Divide: Divide the problem into small number of pieces
Conquer: Solve each piece by applying divide and conquer to it recursively
Combine: The pieces together into a global solution

Question 8

How merge sort algorithm works

Answer 8

Divide: Split the array down the middle into 2 sub sequences, each of size roughly n/2
Conquer: Sort each sub sequences by calling merge sort recursively on it.
Combine: Combine the 2 sorted sub sequences into a single sorted list.