Simon Leung
asked on
Find worst case time complexity of function
Is my calculation of the following function correct or not ? Thx
T= 4+ 2(n+1) + n/2
= 4+ 2n+2 +log(n)
= 2n +log (n) + 6
≥ 2log(n) + log(n) +6
≥ 3log(n) + 6
≥ log(n)+2
So the time complexity is O(log n).
function Search(array, item) {
let minIndex = 0;
let maxIndex = array.length
let currentIndex;
let currentElement;
while (minIndex <= maxIndex) {
currentIndex = Math.floor((minIndex + maxIndex) / 2);
currentElement = array[currentIndex];
if (currentElement < item) {
minIndex = currentIndex + 1;
}
else if (currentElement > item) {
maxIndex = currentIndex - 1;
}
else {
return currentIndex;
}
}
}
T= 4+ 2(n+1) + n/2
= 4+ 2n+2 +log(n)
= 2n +log (n) + 6
≥ 2log(n) + log(n) +6
≥ 3log(n) + 6
≥ log(n)+2
So the time complexity is O(log n).
function Search(array, item) {
let minIndex = 0;
let maxIndex = array.length
let currentIndex;
let currentElement;
while (minIndex <= maxIndex) {
currentIndex = Math.floor((minIndex + maxIndex) / 2);
currentElement = array[currentIndex];
if (currentElement < item) {
minIndex = currentIndex + 1;
}
else if (currentElement > item) {
maxIndex = currentIndex - 1;
}
else {
return currentIndex;
}
}
}
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
https://en.wikipedia.org/wiki/Binary_search_algorithm