Array P&DS | Time Complexity

Question

What is the worst case time complexity of an efficient algorithm (in order of n) to get the last index for an actually filled element, in an array, given the condition that we may not fill the entire initialized array with elements, the array is initialized as “int a[n]; ” [Array may not be filled in a sorted order]

1. O(n)
2. O(1)
3. O(log(n))
4. O($n^2$)

 

Answer 1

The worst case time complexity of an efficient algorithm to get the last index for an actually filled element in an array would be O(n). This is because you would have to check each element in the array one by one until you find the last element that has been filled. You cannot do better than this because you have to check all the elements in the worst case scenario. If the array is not filled in a sorted order, you cannot use a binary search or any other algorithm with a lower time complexity because the array is not sorted and you do not have any other information about the distribution of the elements in the array.

Comments

O(logn ) possible

---

No, In this algorithm with a time complexity of O(log n) is not possible for getting the last index for an actually filled element in an array, given the condition that the array may not be filled in a sorted order because a binary search algorithm, which has a time complexity of O(log n), relies on the input data being sorted or structured in a certain way. Since the array may not be filled in a sorted order, such an algorithm would not be applicable. In worst case time complexity for an efficient algorithm to get the last index for an actually filled element in an array, given the condition that the array may not be filled in a sorted order, would be O(n). So algorithm would need to scan through the entire array, one element at a time, until it finds an element that is not filled.