Big O & ArrayList - Carnegie Mellon University

Big O & ArrayList

15-121 Fall 2020 Margaret Reid-Miller

Today

? Office Hours: Thursday afternoon (time to be announce on Piazza)

? Big O ? Amortized runtime ? ArrayLists

Fall 2020

15-121 (Reid-Miller)

2

How do we determine how efficient (fast) and algorithm is?

Key Idea:

The running time of an algorithm depends on the size of the problem it's solving.

Fall 2020

15-121 (Reid-Miller)

3

Big O: Formal Definition

? Let T(n) ? the number of operations performed in an algorithm as a function of n.

? T(n) O(f(n)) if and only if there exists two constants, n0 > 0 and c > 0 and a function f(n) such that for all n > n0, cf(n) T(n).

Fall 2020

15-121 (Reid-Miller)

4

How long does it take to - say "California" and then - fly to California

The time to fly to California (roughly 6 hours) dominates the time to say "California", so we ignore the time to say "California".

Fall 2020

15-121 (Reid-Miller)

5

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download