Ace Test Series: Algorithms - Time Complexity Notation

Question

If t(n)  and s(n) denotes the time and space complexity of an algorithm with input size n element then which one of the following is always true?

S(n)=O(t(n))   correct

 

 

How???

Answer 1

consider the input size of an algorithm is 'n'. As the space taken by the algorithm is 'n' the time taken wil be vary based on the algorithm such as O(n),O(n^2),O(n^3) etc.But the input size is always n.

Therefore consider S(n) as space complexity i.e is s(n) =n and the time complexity as T(n)=n or n^2 or n^3 etc.

so S(n)<=C.T(n)

Therefore S(n)=O(T(n)).

Comments

If the algorithm want to shift the given array to a new array and we have to access a particular element

---

In this case copying of elements from one array to another array takes time of O(n). (if there are n elements).

The time needed for accessing a particular element O(1) time.So total time complexity is O(n)+O(1)==>O(n)

so both space and time complexity is O(n)

---

In a program you declare an array of size n but there is no loop in the program, so TC will be O(1) but SC will be O(n)

Answer 2

I don't think anything can be said about the relation between space and time complexity in here. The space complexity is going to be big omega(n).

If the algo of binary search then t(n)= O(log n). And if the algo is of selection sort t(n) = O(n^2).