SCC121: weeks 11-15

Question 1

how does input size to and algorithm affect time complexity of a constant algorithm?

Answer 1

-it doesn’t
-best case, worst case and average case remain the same

Question 2

for a linear algorithm, how do we calculate the time complexity?

Answer 2

-directly proportional to input size

Question 3

for a logarithmic algorithm, how do we calculate the time complexity?

Answer 3

-time taken is logarithmically proportional to input size

Question 4

what is sigma notation?

Answer 4

shorthand for expressing addition sums that may be very long

Question 5

what is the downside of a binary search?

Answer 5

can only be performed on a sorted list

Question 6

what is the formal definition of big O?

Answer 6

T(n) is in O(f(n)) if positive constants M and n0 are such that T(n) <= M x f(n) for all n >= n0

Question 7

what is the formal definition of big Omega?

Answer 7

let T(n) and f(n) be two positive functions
T(n) is omega(f(n)) if even as n becomes arbitrarily large, T(n)’s growth is bounded from below by f(n)- it grows no slower than f(n)
T(n) is part of omega(f(n)) if positive constants M and n0 are such that:
T(n) >= M x f(n) for all n >= n0

Question 8

what is the formal definition of big theta

Answer 8

let T(n) and f(n) be two positive functions
T(n) is theta(f(n) if even when n becomes arbitrarily large, T(n)’s growth is bounded from above and below by F(n)- it grows no faster or slower than f(n)
T(n) is part of theta(f(n)) if positive constants M1, M2 and n0 such that:
M1 x f(n) <= T(n)<= M2 x f(n) for all n>= n0