WIA2005 Lecture 1 Asymptotic Notation

What is an algorithm?

• An algorithm is any pseudocode that takes some value, or set of values, as input and produces some value, or set of values, as output.

• An algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output.

• An algorithm is any transformation method that takes some value, or set of values, as input and produces some value, or set of values, as output.

• An algorithm is any programming code that takes some value, or set of values, as input and produces some value, or set of values, as output.

We study algorithm for the following reason, except:

• Algorithms help us to understand scalability.

• Algorithmic mathematics provides a language for talking about program behaviour.

• Correctness is the currency of computing.

• The lessons of program performance generalize to other computing resources.

These are all the properties that an algorithm should have, except:

• There can be no ambiguity as to which step will be performed next.

• It must be composed of a infinite number of steps.

• It must be correct.

• It must terminate.

The rate of growth is _______.

• the rate at which running time is bounded by a function.

• the rate at which the input number is increasing.

• the rate at which running time increases as function of input.

• the rate at which the running time is increasing.

Big O notation represents______.

• the worst time (upper bound)

• the best time (lower bound)

• the average time

What is the asymptotic notation for the following function?

f(n) = n^1/2 + 5

• T(n) = O(n)

• T(n) = O(n^1/2)

• T(n) = O(n) +5

• T(n) = O(n^1/2 + 5)

If function f is bounded below by function g asymtotically, what is the appropriate asymptotic notation?

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

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

• f(n) = O(g(n))

Given two function, f(n) = n³ + 3 and g(n) = n³ . Find the asymptotic growth rate equivalence.

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

• f(n) = O(g(n))

• f(n) = Θ(g(n))

____, if there are positive constants n₀ and c such that at and to the right of n₀, the value of f(n) always lies on or below cg(n).

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

• f(n) = O(g(n))

• f(n) = Θ(g(n))

Give the informal definition for a Big O nothation where a function f is upper bounded by a function g.

• f(n) ≥ k.g(n)

• f(n) = k.g(n)

• f(n) ≤ k.g(n)