Runtime Patterns Flashcards
1
Q
Incrementing/decrementing by a constant.
A
O(n) - i.e. +/-
2
Q
Incrementing/Decrementing by a constant factor
A
O(logn) i.e. */÷
3
Q
While( i > 1)
for(j <- 1 to i)
O(1)
i <- i/2
A
O(n) ? Something to do with how technically both loops are being decremented at the same rate?
4
Q
Incrementing/Decrementing by a constant power
A
O(loglogn) i.e. sqrt(n)/n^2
