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

160 views3 pages
Published on 30 Oct 2018
School
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
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
Unlock document

This preview shows page 1 of the document.
Unlock all 3 pages and 3 million more documents.