How do you calculate time and space complexity?
Answers
Answered by
3
Time and space complexity depends on lots of things like hardware, operating system, processors, etc. However, we don't consider any of these factors while analyzing the algorithm. We will only consider the execution time of an algorithm.
Lets start with a simple example. Suppose you are given an array A and an integer xand you have to find if x exists in array A.
Simple solution to this problem is traverse the whole array A and check if the any element is equal to x.
for i : 1 to length of A if A[i] is equal to x return TRUE return FALSE
Each of the operation in computer take approximately constant time. Let each operation takes c time. The number of lines of code executed is actually depends on the value of x. During analyses of algorithm, mostly we will consider worst case scenario, i.e., when x is not present in the array A. In the worst case, the if condition will run Ntimes where N is the length of the array A. So in the worst case, total execution time will be (N∗c+c). N∗c for the if condition and c for the return statement ( ignoring some operations like assignment of i ).
Lets start with a simple example. Suppose you are given an array A and an integer xand you have to find if x exists in array A.
Simple solution to this problem is traverse the whole array A and check if the any element is equal to x.
for i : 1 to length of A if A[i] is equal to x return TRUE return FALSE
Each of the operation in computer take approximately constant time. Let each operation takes c time. The number of lines of code executed is actually depends on the value of x. During analyses of algorithm, mostly we will consider worst case scenario, i.e., when x is not present in the array A. In the worst case, the if condition will run Ntimes where N is the length of the array A. So in the worst case, total execution time will be (N∗c+c). N∗c for the if condition and c for the return statement ( ignoring some operations like assignment of i ).
Similar questions