{"id":715,"date":"2020-06-08T01:44:08","date_gmt":"2020-06-08T01:44:08","guid":{"rendered":"http:\/\/learnlearn.uk\/alevelcs\/?page_id=715"},"modified":"2023-03-13T07:41:26","modified_gmt":"2023-03-13T07:41:26","slug":"big-o-notation-searching-sorting","status":"publish","type":"page","link":"https:\/\/learnlearn.uk\/alevelcs\/big-o-notation-searching-sorting\/","title":{"rendered":"Big O Notation with Searching & Sorting"},"content":{"rendered":"
\n

Introduction<\/h2>\n
\n\n

What is Big O Notation?<\/h3>\n

Big O notation is used used as a tool to describe the growth rate of a function in terms of the number of instructions that need to be processed (time complexity) or the amount of memory required (space complexity).<\/p>\n

This allows different algorithms to be compared in terms of their efficiency.<\/p>\n

Note: Two algorithms can have the same Big O notation but in practice have wildly different execution times in practice. This is because the Big O describes the growth rate of complexity, not the actual complexity itself.<\/p>\n

Time Complexity<\/strong><\/p>\n

Time complexity refers to the growth in the number of instructions executed (and therefore the time taken) as the length of the array to be searched increases.<\/p>\n

Space Complexity<\/strong><\/p>\n

Space complexity refers to the growth in the size of memory space that is required as the length of the array is increased.<\/p>\n

Algorithm Performance<\/strong><\/p>\n

There are a number of factors that affect the performance of search \/ sorting algorithms. Some algorithms perform well with high entropy (randomness) data, other algorithms work better when the data is partially sorted in some manner. This means that no one algorithm works best in every situation and the nature of the data being sorted needs to considered.<\/p>\n