3.1 Time Complexity and Asymptotic Notation

Question 1

Sorting

Answer 1

❑Sorting is one of the most common tasks in data analysis
❑Examples:
❑Print out a collection of employees sorted by salary
❑Print out a list of names in alphabetical order
❑There are many sorting algorithms
❑The Selection Sort algorithm repeatedly finds the smallest element in the unsorted tail region of a list and moves it to the front

Question 2

Search Algorithms

Answer 2

❑Searching Algorithms: check for an element from any data structure where it is stored
❑Classed into two categories:
❑Sequential Search e.g.linear search
❑The list is traversed sequentially, and every element is checked
❑The list does NOT need to be sorted
❑Interval Search e.g.binary search
❑A ‘divide and conquer’ algorithm
❑The list MUST be sorted

Question 3

Binary Search VS Linear Search

Answer 3

❑Binary search is an O(log2(n)) algorithm
❑elements →n/2 elements →n/4 elements →…. →1 element
❑Linear search algorithm of order O(n)
❑Which algorithm is faster?
❑Binary search algorithm is much faster, Butit only works on sorted data….
❑Binary search examples?
❑Spell checkers, phone books, dictionaries…

Question 4

❑Which algorithm is faster?

Answer 4

❑Binary search algorithm is much faster, Butit only works on sorted data….
❑Binary search examples?
❑Spell checkers, phone books, dictionaries…

Question 5

Asymptotic Algorithm Analysis

Answer 5

❑The asymptotic analysis of an algorithm determines the running time in Big-Oh notation

Question 6

how to perform the asymptotic analysis

Answer 6

❑We find the worst-case number of primitive operations executed as a function of the input size, T(n)
❑We express this function with Big-Oh notation
❑Big-Oh Notation defines an upper bound of an algorithm (worst-case) ❑The runtime in terms of how quickly it grows relative to the input –as the input gets larger

Question 7

The Big-Oh Runtime Analysis

Answer 7

❑Step 1: Find out the input and what represents
❑Step 2: Calculate the primitive operations of the algorithm in terms of n
❑Step 3: Drop the lower-order terms
❑Step 4: Remove all constant factors

Question 8

Polynomial Time

Answer 8

An algorithm is solvable in polynomial timeif the number of steps required to complete the algorithm for a given input is O(nk) for some non-negative integer k, nbeing the complexity of the input.

Question 9

The Classes of Algorithms

Answer 9

Problems are divided up into a number of classes (classifications):
❑Computable
❑Problems that can be solved using a computer
❑e.g. f(x) = x+ 1
❑Non-Computable
❑Problems that can be solved using a computer
❑e.g. Halting Problem
❑Can we find a program that can predict whether any other program and its input will halt or run forever…

Question 10

P-Problems

Answer 10

Solved in a reasonable amount of time (polynomial time
E.g. multiplication and sorting

Question 11

NP Problems

Answer 11

❑Difficult to solve in a reasonable amount of time but easy to verifythe solution
❑Non-deterministic algorithms
❑Problems involving decision making
❑Important class of problems e.g. job scheduling, circuit design, vehicle routing etc

Question 12

NP-HARDProblems

Answer 12

❑Very, very difficult to solve problems, which cannot be done in a reasonable amount of time
❑The exhaustive search is not polynomial
❑They are very difficult to verify in polynomial time

Question 13

NP-COMPLETE Problems

Answer 13

❑The hardest problems in NP set
❑Complexities greater than polynomial time
❑The exhaustive search is not polynomial
❑Verifiable in polynomial time
❑No polynomial-time algorithm is discovered for any NP-complete problem
❑Nobody was able to prove that no polynomial-time algorithm exist for any of the problem

Question 14

Examples of NP-Complete Problems

Answer 14

❑The travelling sales person problem
❑Finding the shortest common superstring
❑Checking whether two finite automata accept the same language
❑Given three positive integers a, b, and c, do there exist positive integers (x and y) such that ax2+ by2= c

Question 15

Consequences of P=NP

Answer 15

❑If this was found to be true, the news would make WORLD HEADLINES!
❑Modern society as we know it would be completely and utterly DOOMED!
❑All passwords could be cracked in polynomial time (very, very fast)
❑You would not be able to secure any computer or device on the internet, wireless or mobile networks…..
❑Algorithms that currently take years might take minutes!
❑Proof [that NP≠P] was put forward in 2010, but has since been refuted..