IB Computer Science/Abstract Data Structures and Algorithms
From Wikibooks, the open-content textbooks collection
Standard Level
Topic 1 - Systems Life Cycle and Software Development — Topic 2 - Program Construction in Java — Topic 3 - Computing System Fundamentals —
Higher Level
Topic 4 - Computer Mathematics and Logic — Topic 5 - Abstract Data Structures and Algorithms — Topic 6 - Further System Fundamentals — Topic 7 - File Organization
Extras
Program Dossier — Case Study
| Please note: Any IB syllabus statements included here are NOT under any free license and remain property of the IBO. They are reproduced here for personal study purposes only. Return to International Baccalaureate |
Return to IB Computer Science
Contents |
[edit] Abstract Data Structures and Algorithms
[edit] Fundamentals
[edit] Static data structures
[edit] Dynamic data structures
[edit] Objects in problem solutions
[edit] Recursion
[edit] Algorithm Evaluation
[edit] Efficiency of Algorithms
To optimize algorithms, one must first know whether a certain algorithm is better or worse than another one. In this case, better can mean that the algorithm processes data faster or that less RAM is used. To measure data processing speed, one can use Big O notation.
Big O notation is always in the form of O(expression). The expression inside the parentheses is different for different efficiencies. It almost always contains n, the number of items of data to be processed. The Big O notation of a linear search on an array (of size n) is O(n). This means that doubling the array size will, on average, double the time for the linear search to complete.
Big O notation does not, however, indicate exactly how efficient an algorithm is. It only indicates how much the time spent increases when n is very large and is increased. For instance, if a certain algorithm takes 0.5n + 2 milliseconds for each item of data, it will still have a Big O notation of O(n). This is because when n gets to, say, one trillion, the added 2 will have almost no effect, so it is discarded. In the same way, all coefficients of n are discarded.
Other examples of Big O notation include O(n2) for bubble and selection sort and O(logn) for binary search. Note that binary search’s Big O notation is logn instead of log2n, because logarithms of different bases increase in approximately the same way when n is large.
