What is the time complexity (in Big-O notation) of thealgorithm with respect to
ID: 3858631 • Letter: W
Question
What is the time complexity (in Big-O notation) of thealgorithm with respect to the size of the playlist?
How does this time complexity compare to the time complexity of binary search (in terms of Big-O)?
//Coded Algorithm that will break the program into 3 sublists
// Encorperates a binary search in order to search through an array
// performs a binary search on an array.
#include <iostream>
#include <string.h>
using namespace std;
// Declaring the functions that will be called in the main function
// Can be declared and wrote immediately but doesn’t matter
void sortStr(string [], int);
int binary_Search(string [], string);
int len;
int main()
{
// Array with songs not in a particular order and will be ordered
// alphabetically in the program
string songs[] = {"My Curse","Holy Diver","Heartbeat","Hurt","Bat Country",
"Fall Apart","Congradulations","End of Heartache","Hold My Hand","I Remember You","Really Really",
"Believe","Rain"};
// Global Variables that will be utilized.
string songName;
int res;
len=sizeof(songs)/sizeof(songs[0]);
//Send the Array through the sorting function
sortStr(songs, len);
cout<<"Songs after going through Ordering Function"<<endl;
//List out the songs in alphabetical order
for(int i=0;i<len;i++)
cout<<"songs["<<i<<"]= "<< songs[i]<<endl;
//Allow user to search for a song in the array and it will display the element
cout << "Please enter a song name: ";
getline(cin, songName);
// Search for name
res = binary_Search(songs, songName);
// If results contains -1 the name was not found.
if (res == -1)
cout << "That song does not exist in the playlist. ";
else
{
// If not returned -1 then output the song and its location
cout << "That song is found at element " << res;
cout << " in the play list. ";
}
return 0;
}
void sortStr(string songs[], int num)
{
int start, minin;
string minVal;
for (start = 0; start < (num - 1); start++)
{
minin = start;
minVal = songs[start];
for(int in = start + 1; in < num; in++)
{
if (songs[in] < minVal) //Actual Swapping section when parameter passed
{
minVal = songs[in];
minin = in;
}
}
songs[minin] = songs[start]; //Else swap a different way
songs[start] = minVal;
}
}
int binary_Search(string songs[], string val)
{
int start = 0, // start song array element
end = len - 1, // end of song array element
mid1, mid2, // Mid point of search
position = -1; // Position of search value
bool found = false; // Setting a flag to determine whether the while loop will r
while (!found && start <= end)
{
mid1 = start+ ( end - start) / 3; // Calculate mid1 point
mid2 = start + 2 * ( end - start) / 3 ;
// Calculate mid2 point
if (songs[mid1] == val) // If value is found at mid1
{
found = true;
position = mid1;
}
else if (songs[mid2] == val) // If value is found at mid2
{
found = true;
position = mid2;
}
else if (songs[mid1] > val ) // If value is in lower 1/3
end = mid1 - 1;
else if(songs[mid2] < val)
start = mid2 + 1;
// If value is in 2/3 rd places
else
{
start = mid1;
end = mid2;
}
}
return position;
}
Explanation / Answer
Solution :
- Here firstly playlist is sorted in alphabetical order.
sortStr() function sorts the song names in array.
sortStr() uses selection sort to sort the playlist.
Here inner for loop is executed given number of times = (n-1) + (n-2) +....+2+1 = sum(1,2,..n-1) =O(n2).
- Then All songs are printed in alphabetical order. Which takes O(n) time.
- Now In given code, binary search is used to search song in playlist.
It takes O(log n) time.
Hence total time complexity for given algorithm = O(n2) + O(n) + O(log n) = O(n2).
Where n is number of songs in playlist.
Normal binary search takes O(log n) time.
- In given code, Firstly sorting is done using O(n2) time then songs are printed and then binary search is used to search a song.
Hence given code has higher complexity compared to binary search.
If you have any doubts then you can ask in comment section.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.