Data structures are applied using algorithms, which manipulate the data of the data structure ("Data Structures: Lecture 2", n.d.). In order to make our algorithms most efficient, we need to think of what makes a more efficient algorithm. That is done by having knowledge of time complexity and space complexity.
Time complexity describes the amount of time a algorithm takes in connection with the amount of input to the algorithm. The time it takes for an algorithm to process the input is the number of memory assesses performed. If that being the number of comparisons, the number of times a inner loop needs to be executed ("Data Structures: Lecture 2", n.d.).
Space complexity is the amount of memory used by the algorithm (including the input values to the algorithm) to execute and produce the result ("Space Complexity of Algorithms | Studytonight", n.d.)
Searching and Sorting algorithms are two distinct things, but both correlate together when we consider developing structured programs and the way we use them to retrieve specific data in a set or collection in the program. An algorithm takes an input instance and turns it to the desired output (Skiena, 2008). The data input for the algorithm is usually an n-element array, each is part of a collection of data and each has a key that is the value to be sorted (Cormen et al., 2009).
A sorting algorithm describes the method by which we determine the sorted order in which can be numbers, names etc. Steven Skiena described in his book The Algorithm Design Manual (Skiena, 2008, p. 103), that sorting is worth our attention for several reasons such as:
- Sorting is the basic building block that many algorithms are built around. Understanding sorting we obtain an amazing amount of power to solve other problems.
- Most of the interesting ideas used in the design of algorithms appear in the context of sorting, such as divide-and-conquer, data structures, and randomized algorithms
- Computers have historically spent more time sorting than doing anything else.
When an array is already sorted and we need to search for a particular element, it will cut down on the time it takes to find the element because we can use different searching algorithms that are good for searching sorted arrays. Sorting an array takes it’s own amount of time to complete, then we would need to search the array for the element we are looking for. As the size of the elements in the array increases so does the time it takes to search or sort the array.
Choosing one design over another is a task that developers deal with on a daily basis and need to keep the benchmarks of time complexity and space complexity in mind when structuring programs.
References
Data Structures: Lecture 2.
Cs.utexas.edu. Retrieved from http://www.cs.utexas.edu/users/djimenez/utsa/cs1723/lecture2.html.
Skiena, S. (2008). Algorithm
Design Manual, The (2nd ed., p. 103). Springer.
Space Complexity of Algorithms |
Studytonight. Studytonight.com. Retrieved from https://www.studytonight.com/data-structures/space-complexity-of-algorithms.
