CS234 Lecture Notes - Lecture 7: Concatenation, 5,6,7,8, Logarithm

27 views4 pages
8 Feb 2016
Course
Professor
Lecture 7 Complexity Analysis
Last time:
Evaluating complexity of given code
Big-O notation, Big-Ω, Big-
Common complexity classes
Example
 
is since if c = 2,  and
is Ω since if c =
,
 
  is
Properties of Big-O
1) Sum
  is  
E.g.   then   
2) Multiplication by constant
* is  for all  
E.g. is 
𝑇𝑛 is 𝜃𝑓𝑛 if and only if
𝑇𝑛
is Ω
𝑓𝑛
and
𝑇𝑛
is O
𝑓𝑛
i.e.
  𝑐
*
𝑓𝑛𝑇𝑛𝑐
*
𝑓𝑛
1
𝑛
𝑛 
𝑛 
Unlock document

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

Already have an account? Log in

Get access

Grade+
$10 USD/m
Billed $120 USD annually
Homework Help
Class Notes
Textbook Notes
40 Verified Answers
Study Guides
1 Booster Class
Class+
$8 USD/m
Billed $96 USD annually
Homework Help
Class Notes
Textbook Notes
30 Verified Answers
Study Guides
1 Booster Class