CS Intro

Question 1

Big O Notation

Answer 1

Big O notation is used in Computer Science to describe the performance or complexity of an algorithm. Big O specifically describes the worst-case scenario, and can be used to describe the execution time required or the space used (e.g. in memory or on disk) by an algorithm.

Question 2

O(1)

Answer 2

describes an algorithm that will always execute in the same time (or space) regardless of the size of the input data set.

Question 3

O(N)

Answer 3

describes an algorithm whose performance will grow linearly and in direct proportion to the size of the input data set. The example below also demonstrates how Big O favours the worst-case performance scenario; a matching string could be found during any iteration of the for loop and the function would return early, but Big O notation will always assume the upper limit where the algorithm will perform the maximum number of iterations.

Question 4

O(N^2)

Answer 4

represents an algorithm whose performance is directly proportional to the square of the size of the input data set. This is common with algorithms that involve nested iterations over the data set. Deeper nested iterations will result in O(N^3), O(N^4) etc.

Question 5

O(2^N)

Answer 5

REALLY big!

denotes an algorithm whose growth doubles with each additon to the input data set. The growth curve of an O(2^N) function is exponential - starting off very shallow, then rising meteorically.

Question 6

O(logN)

Answer 6

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.

Question 7

What is a logarithm?

Answer 7

a quantity representing the power to which a fixed number (the base) must be raised to produce a given number.

Question 8

Recursion

Answer 8

Reduce a problem to a simpler (or smaller) version of the same problem, plus some simple computa0ons
• Recursive step
– Keep reducing un0l reach a simple case that can be solved directly
• Base case

def recurMul(a, b): 
    if b == 1: 
       return a 
    else: 
       return a + recurMul(a, b-1)

Question 9

Recursive palindrome check

Answer 9

def isPalindrome(s):

    def toChars(s): 
        s = s.lower() 
        ans = '' 
        for c in s: 
            if c in 'abcdefghijklmnopqrstuvwxyz': 
                ans = ans + c 
return ans 

    def isPal(s): 
        if len(s) <= 1: 
            return True 
        else: 
            return s[0] == s[-1] and isPal(s[1:-1]) 

return isPal(toChars(s))

Question 10

Polynomial complexity

Answer 10

O(n^c) - usually happens with nested loops

Question 11

Exponential complexity

Answer 11

O(c^n) - Recursive func4ons where more than one recursive call for each size of problem

Question 12

How to deal with large complexity in big applications?

Answer 12

Need algorithms that can approximate. Hard to write new algorithms, so use what’s out there.

Question 13

Hashing

Answer 13

Convert key to an int
• Use int to index into a list (constant 9me)
• Conversion done using a hash func)on
– Map large space of inputs to smaller space of
outputs
– Thus a many-to-one mapping
– When two inputs go to same output – a collision
– A good hash func9on has a uniform distribu9on – minimizes probability of a collision