LAD Block 3: Analysis and design of algorithms

  1. Describe O(1)
    • Constant.
    • Describes an algorithm that will always execute in the same time (or space) regardless of the size of the input data set.
  2. Describe O(log(n))
    • logarithmic.
    • This type of algorithm is described as O(log N). The iterative halving of data sets described in the binary search example produces a growth curve that peaks at the beginning and slowly flattens out as the size of the data sets increase e.g. an input data set containing 10 items takes one second to complete, a data set containing 100 items takes two seconds, and a data set containing 1000 items will take three seconds. Doubling the size of the input data set has little effect on its growth as after a single iteration of the algorithm the data set will be halved and therefore on a par with an input data set half the size. This makes algorithms like binary search extremely efficient when dealing with large data sets.
  3. Describe O(n)
    • Linear.
    • O(N) describes an algorithm whose performance will grow linearly and in direct proportion to the size of the input data set.
  4. Describe O(n^2)
    • Quadratic.
    • O(2N) denotes an algorithm whose growth doubles with each additon to the input data set. The growth curve of an O(2N) function is exponential - starting off very shallow, then rising meteorically.
  5. What does O(N*M) mean?
    For every element in N go through all elements in M, the m loop is nested inside the N loop.
  6. Describe O(N*log(N))
    • int n = 100
    • for(int i = 0; i < n; i++) {
    • //this loop is executed n times, so O(n)

    • for(int j = n; j > 0; j/=2)
    • //this loop is executed O(log n) times
    • {

    •  }
    • }
    • How many times can I divide n by 2. It turns out that this is in O (log n).
    • So you are executing a loop n times and within that loop you are executing another loop log(n) times so you have O(n)*O(log n) --> O(n log n)
Card Set
LAD Block 3: Analysis and design of algorithms
LAD Block 3: Analysis and design of algorithms