Big O notation notes

Question 1

what is the purpose of Big O notation ?

Answer 1

to evaluate the complexity of an algorithim

Question 2

what is complexity ?

Answer 2

complexity = Time ( no of operations)
space( how much memoery an algorithim needs )

Question 3

what is
O(1)
O(n)
O(n^2)

Answer 3

O(1) - will always take the same amount of memory

O(n) - grows at the same rate as number of elements t

O(n^2) - time take inceases at a polynomical rate

Question 4

what is
O(2^n)
O(n!)
O(logn)

Answer 4

O(2^n) - time doubles with each data item

O(n!) time grows expontially

O(logn) time grows slowly

Question 5

state the complexity of
O(1)
O(n)
O(n^2)
O(2^n)
O(n!)
O(logn)

Answer 5

O(1) -constant complxity
O(n)- linear complexity
O(n^2)]- quadratic complexity
O(2^n)- exponential complexity
O(n!)-factorial complexity
O(logn)- logarithimic complexity

Question 6

what are the complexities of all the search algorithms ?
best and avg(worst)?

Answer 6

Best: Avg:
inear search -o(1) o(n)
binary search-o(1) o(logn)

Question 7

what are the complexities for all the sort algorithms ?
best and avg(worst)

Answer 7

Best: avg:

bubble sort -o(n) o(n^2)
insertion -o(n) o(n^2)
merge sort -o(nlogn) o(nlogn)
quick sort -o(nlogn) o(nlogn)