# ECS 36A Lecture Notes - Lecture 10: Big O Notation, Big Two, Sorting Algorithm

160 views3 pages

Published on 30 Oct 2018

School

Department

Course

Professor

ECS 36A - Lecture 10 - Sorting

e(g(n)) = { f(n) Ǝ C1, C2, n0 s.t., ∀ n> n0, C , g(n) <= f(n) <= c2g(n) } : f(n) = function of interest,

C = some constant, n is to show that we are interested in bounds as the function goes to infinity

“The

order of magnitude

function describes the part of T(n) that increases the fastest as

the value of n increases.” →

This is called the Big-O notation.

True or False Practice:

1000 ϵ θ(n) -- false

1000n ϵ θ(n) -- true

n2 + logn ϵ θ(n2) -- true

N log n ϵ θ(n) -- false

(have to consider which grows faster, is statement 1 bounded by theta or

no?)

Summation of P-1 with i starting at 0: aini ϵ θ(N(P-1) ) -- True

Log base a of n ϵ θ(log6 n) -- true

Proper vs Casual Notation of these Problems:

- The formal way to write these statements is as presented in the examples,using the ϵ

- However, it is common that computer scientists instead use an “=” sign -- for our

practice, they are interchangeable and mean the same thing -- this one is just a little

more informal

Big Theta defines a tight bound around the thing of interest (the outputs of a program, its

runtime, its iterations, etc) → this makes it harder to calculate because this level of precisity is

difficult to obtain

Example for Comprehension

--- if we were asked to create a tight bound of the income of residents in Palo Alto, creating that

finite range would be difficult to obtain

-- However, if asked to create a Lower Bound, it would not be as hard because this

automatically captures everything above (e.g. if we calculate that a $200,000 income is needed

to live in Palo Alto, this stands true for every resident who makes well over $200,000) → easier

to work with

Example #2 for Comprehension

-- While making an auto-pilot program, the run-time has to be faster than a certain threshold

(Lower Bound) to avoid crashes -- if it’s faster then said threshold, that becomes a plus and

adds to efficiency