less time by using more storage space or by solving a given algorithm in very little space by spending more time. To solve a given programming problem, many different algorithms may be used. Some of these algorithms may be extremely time-efficient and others extremely space-efficient. Time/space trade off refers to a situation where you can reduce the use of memory at the cost of slower program execution, or reduce the running time at the cost of increased memory usage.
The best algorithm to solve a given problem is one that requires less space in memory and takes less time to execute its instructions to generate output. . . Asymptotic Notations Asymptotic Notations are languages that uses meaningful statements about time and space complexity.
The following three asymptotic notations are mostly used to represent time complexity of algorithms: (i) Big O Big O is often used to describe the worst-case of an algorithm. (ii) Big Ω Big Omega is the reverse Big O, if Bi O is used to describe the upper bound (worst - case) of a asymptotic function, Big Omega is used to describe the lower bound (best-case). 12th Computer Chapter - - (iii) Big Θ When an algorithm has a complexity with lower bound = upper bound, say that an algorithm has a complexity O (n log n) and Ω (n log n), it’s actually has the complexity Θ (n log n), which means the running time of that algorithm always falls in n log n in the best-case and worst-case. .
. Best, Worst, and Average ease Efficiency Let us assume a list of n number of values stored in an array. Suppose if we want to search a particular element in this list, the algorithm that search the key element in the list among n elements, by comparing the key element with each element in the list sequentially. The best case would be if the first element in the list matches with the key element to be searched in a list of elements.
The efficiency in that case would be expressed as O( ) because