Class Notes (1,100,000)
US (480,000)
Rutgers (10,000)
4:18 (400)
Lecture 20

01:198:111 Lecture 20: CS111 Runtime


Department
Computer Science
Course Code
01:198:111
Professor
GUNAWARDENA
Lecture
20

This preview shows half of the first page. to view the full 2 pages of the document.
Runtime
Efficiency of an algorithm is based on
Operations
Assignment
Comparison
Increment
T(n) = number of operations
For loops multiply the operations inside
Inside loop is 3 operations → (3n)
M(n) = amount of memory used for n data set
Total operations that the algorithm performs
Best
Average
Worst cases
How much memory is used by the algorithm
Int Variable = 4 bytes
Array = 4n
Ex: 3 int variables + 1 array = 4n + 12 bytes of memory
Best
Average
Worst cases
Search Function
T(n) = 1*n = n
Big O
The notation for describing efficiency
A mathematical language
Order of functions, fastest to slowest efficiency
1
Constant
Big O = O(1)
log(n)
Logarithmic
O(log(n))
N
Linear
O(n)
You're Reading a Preview

Unlock to view full version