Fill the following table giving the worst case time complexi

Fill the following table giving the worst case time complexity in O notation: Suppose an algorithm is O(n^3). What effect do you expect on the running time when you double the input size? Express the following functions in terms of their O notation: 100 n + 53, 3n^2 + 5n, 10n + 0.005 n log n, 0.0001 n^3 + 500 n^2 + 500.

Solution

Unsorted Array
(No Duplicates)

b) When talking about complexity of a method we care about how the number of operations relates to the problem size. So if the complexity of an algorithm is O(n^3) it means the order of growth is n^3. So if the input size is doubled then if earlier the input size was n and now the size is 2n, the complexity will remain O(n^3) as long as there is constant with n.

	Unsorted Array (No Duplicates)	Unsorted Array	Sorted Array
Find	O(n)	O(n)	O(logn) using binary search
Insert	O(n) (Because you have to check all elements before inserting)	O(1)	O(n) (Because elements need to be shifted)
Delete	O(n)	O(n)	O(logn)