Introduction to Programming (in C++) Complexity Analysis of

Introduction to Programming (in C++) Complexity Analysis of

Introduction to Programming (in C++) Complexity Analysis of Algorithms Jordi Cortadella Dept. of Computer Science, UPC Estimating runtime What is the runtime of g(n)? void g(int n) { for (int i = 0; i < n; ++i) f(); } void g(int n) {

for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) f(); } Introduction to Programming Dept. CS, UPC 2 Estimating runtime What is the runtime of g(n)? void g(int n) { for (int i = 0; i < n; ++i)

for (int j = 0; j <= i; ++j) f(); } Introduction to Programming Dept. CS, UPC 3 Complexity analysis A technique to characterize the execution time of an algorithm independently from the machine, the language and the compiler. Useful for:

evaluating the variations of execution time with regard to the input data comparing algorithms We are typically interested in the execution time of large instances of a problem, e.g., when n , (asymptotic complexity). Introduction to Programming Dept. CS, UPC 4 Big O

A method to characterize the execution time of an algorithm: Adding two square matrices is O(n2) Searching in a dictionary is O(log n) Sorting a vector is O(n log n) Solving Towers of Hanoi is O(2n) Multiplying two square matrices is O(n3) The O notation only uses the dominating terms of the execution time. Constants are disregarded. Introduction to Programming Dept. CS, UPC

5 Big O: formal definition Let T(n) be the execution time of an algorithm with input data n. T(n) is O(f(n)) if there are positive constants c and n0 such that T(n) cf(n) when n n0. cf(n) T(n) n

n0 Introduction to Programming Dept. CS, UPC 6 Big O: example Let T(n) = 3n2 + 100n + 5, then T(n) = O(n2) Proof: Let c = 4 and n0 = 100.05 For n 100.05, we have that 4n2 3n2 + 100n + 5

T(n) is also O(n3), O(n4), etc. Typically, the smallest complexity is used. Introduction to Programming Dept. CS, UPC 7 Big O: examples Introduction to Programming Dept. CS, UPC

8 Complexity ranking Introduction to Programming Dept. CS, UPC 9 Complexity analysis: examples Let us assume that f() has complexity O(1) for (int i = 0; i < n; ++i) f(); for (int i = 0; i < n; ++i)

for (int j = 0; j < n; ++j) f(); for (int i = 0; i < n; ++i) for (int j = 0; j <= i; ++j) f(); for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) for (int k = 0; k < n; ++k) f(); for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) for (int k = 0; k < p; ++k) f(); Introduction to Programming Dept. CS, UPC

10 Complexity analysis: recursion void f(int n) { if (n > 0) { DoSomething(n); // O(n) f(n/2); } } Introduction to Programming Dept. CS, UPC

11 Complexity analysis: recursion void f(int n) { if (n > 0) { DoSomething(n); // O(n) f(n/2); f(n/2); } } Introduction to Programming Dept. CS, UPC

12 Complexity analysis: recursion void f(int n) { if (n > 0) { DoSomething(n); // O(n) f(n-1); } } Introduction to Programming Dept. CS, UPC

13 Complexity analysis: recursion void f(int n) { if (n > 0) { DoSomething(); // O(1) f(n-1); f(n-1); } } Introduction to Programming Dept. CS, UPC

14 Asymptotic complexity (small values) Introduction to Programming Dept. CS, UPC 15 Asymptotic complexity (larger values) Introduction to Programming

Dept. CS, UPC 16 Execution time: example Let us consider that an operation can be executed in 1 ns (10-9 s). Introduction to Programming Dept. CS, UPC 17

Recently Viewed Presentations

  • An Introduction to Writing Impact into Funding Applications

    An Introduction to Writing Impact into Funding Applications

    An Introduction to Writing Impact into Funding Applications Summary Context of impact Staying competitive How to formulate impact statements within the Je-S application system Research planning - possible routes to research-led impact Questions Context: 'Excellence with Impact' Research and innovation...
  • VHS internationella antagningsomgng - Rekrytering och sktryck 1(2)

    VHS internationella antagningsomgng - Rekrytering och sktryck 1(2)

    VHS internationella antagningsomgång - Rekrytering och söktryck 1(2) . 2011-04-29. Avdelningen för analys och utvärdering Katarina Borne. S1HEP_JAPA, uppgift saknas. Uppgifter som är användbara i deltema A.2 är hämtade från NyA, beräkningar från Ladok, och NyA uppföljning (som får uppgifter...
  • Catabolite Repression, Inducer Exclusion, and Diauxic Growth

    Catabolite Repression, Inducer Exclusion, and Diauxic Growth

    Inducer Exclusion. Enzyme IIA glc (without P) acts as inhibitor of lacpermease. Lactose not taken into cell. Lactose not converted to allolactose by β-galactosidase. Repressor Protein stays on operator. Catbolite Repression. Enzyme IIA glc - P not available.
  • x?

    x?

    Year 6, Topic 1, Switched on Science Classifying Critters
  • Computer History CSCE 101 Computer History In 40

    Computer History CSCE 101 Computer History In 40

    Alan Turing. During WWII Turing created an electromechanical machine to break German Ciphers. ... Invented by Jack Kilby, Nobel Laureate of Physics. IBM 360. Small and large applications. Commercial and Scientific applications. From 8K to 8M of memory.
  •   . Instruments in gynecology Artery Forceps  used for

    . Instruments in gynecology Artery Forceps used for

    Babcock's Forceps. The tip is atraumatic as there are no sharp tooth. it used. for grasping tubular structures. like: fallopian tube in tubectomyin modified Pomeroy's operation
  • WEATHERIZATION ENERGY AUDITOR SINGLE FAMILY Generating a Work

    WEATHERIZATION ENERGY AUDITOR SINGLE FAMILY Generating a Work

    The double brick chimney serving the warm air furnace is coated with roof tar and in contact with the framing. Because the chimney serves a relatively low flue temperature (as opposed to a wood stove) lining it should suffice to...
  • Little Data, Big Data Translational Research Partners Across

    Little Data, Big Data Translational Research Partners Across

    The Sackler Institute for Nutrition Science, a program of the New York Academy of Sciences, partnered with The Rockefeller University Sackler Center for Biomedicine and Nutrition, The Rockefeller University Center for Clinical and Translational Science, and Clinical Directors Network (CDN),...