6) What is time complexity?
A) Time complexity of algorithms
• When you need to write a program that needs to be reused many times other issues may arise
– how much times does it take to run it?
– how much storage space do its variables use?
– how much network traffic does it generate?
• For large problems the running time is what really determines whether a program should be used
• To measure the running time of a program, we – Select different sets of inputs that it should be tested on (for benchmarking).
Such inputs may correspond to
• the easiest case of the problem that needs to be solved(best case)
• the hardest case of the problem that needs to be solved(worse case)
• a case that falls between these two extremes(average case)
• In many cases, the running time of a program depends on a particular type of input, not just the size of the input
– the running time of a factorial program depends on the particular number whose factorial is being sought because this determines the total number of multiplications that need to be performed
– the running time of a search program may depend on whether the value being sought occurs in the collection of items to be searched
• To assess the running time, we have to accept the idea that certain programming operations take a fixed amount of time (independent of the input size):
– arithmetic operations (+, , *, etc.)
– logical operations (and, or, not)
– comparison operations (==, <, >, etc.)
– array/vector indexing

simple assignments (n = 2, etc.)
Notation

Name

Example


constant

Determining if a number is even or odd


iterated logarithmic

The find algorithm of Hopcroft and Ullman on a disjoint set


logarithmic

Finding an item in a sorted list with the binary search algorithm


polylogarithmic

Deciding if n is prime with the AKS primality test


fractional power

searching in a kdtree


linear

Finding an item in an unsorted list


linearithmic, loglinear, or quasilinear

Sorting a list with heapsort, computing a FFT


quadratic

Sorting a list with insertion sort, computing a DFT





polynomial, sometimes called algebraic

Finding the shortest path on a weighted digraph with the FloydWarshall algorithm


exponential, sometimes called geometric

Finding the (exact) solution to the traveling salesman problem (under the assumption that P ≠ NP)


factorial, sometimes called combinatorial

Determining if two logical statements are equivalent [1], traveling salesman problem, or any other NP Complete problem via bruteforce search


double exponential

Finding a complete set of associativecommutative unifiers [2]

Notation

Definition

Mathematical definition

Alternative definition


asymptotic upper bound




asymptotic lower bound




asymptotically tight bound




asymptotically negligible




asymptotically dominant



Share with your friends: