Analysis of Algorithms

Question 1

How do you work out the time for an algorithm to be executed?

Answer 1

T(n) = C op x C(n)

Where C op is the time to execute the basic operation on a computer, and C(n) is the number of times it needs to be executed.

Question 2

Big O notation definition

Answer 2

A function t(n) is said to be in the O(g(n)) denoted by t(n) = O(g(n)) if there exists some positive constant c and some nonnegative integer n0 such that:

t(n) <= cg(n), n>= n0.

lecture 5 if you dont understand

Question 3

Small o notation definition

Answer 3

Strict upper bound.

A function t(n) is said to be in the o(g(n)) denoted by t(n) = o(g(n)) if there exists some positive constant c and some nonnegative integer n0 such that:
t(n) < cg(n), n >= n0. Not equal to.

Example g(n) = o(n^2), g(n) CANNOT be quadratic

Question 4

Omega notation Ω

Answer 4

A function t(n) is said to be in the Ω(g(n)) denoted by t(n) = Ω(g(n)) if there exists some positive constant c and some nonnegative integer n0 such that:

t(n) >= cg(n), n >= n0, greater

Big Omega is inverse of Big O

Question 5

Theta notation θ

Answer 5

A function t(n) is said to be in the θ(g(n)) denoted by t(n) = θ(g(n)) if there exists some positive constant c1 and c2 and some nonnegative integer n0 such that:

c1 g(n) <= t(n) <= c2 g(n), n > n0

you do t(n) = 0(g(n)) and t(n) = Ω(g(n))

Question 6

log b x = ?

Answer 6

log b x = ( log a x ) / ( log a b)

Question 7

c = O(?)

Answer 7

c = O(1) for any constant c