please tell me the time complexity of algorithm given below ?

Question

#include <bits/stdc++.h>
using namespace std;

stack<int> sortStack(stack<int> input)
{
stack<int> tmpStack;

while (!input.empty())
{
int tmp = input.top();
input.pop();

while (!tmpStack.empty() &&
tmpStack.top() < tmp)
{

input.push(tmpStack.top());
tmpStack.pop();
}

tmpStack.push(tmp);
}

return tmpStack;
}

void sortArrayUsingStacks(int arr[], int n)
{

stack<int> input;
for (int i=0; i<n; i++)
input.push(arr[i]);

stack<int> tmpStack = sortStack(input);

for (int i=0; i<n; i++)
{
arr[i] = tmpStack.top();
tmpStack.pop();
}
}

int main()
{
int arr[] = {10, 5, 15, 45};
int n = sizeof(arr)/sizeof(arr[0]);

sortArrayUsingStacks(arr, n);

for (int i=0; i<n; i++)
cout << arr[i] << " ";

return 0;
}

Answer 1

Hi Bahubali,

Actually, the example str="Helloworld " is good because it only has a word and is easy to analyse.

So, when the for loop finally find the space at the end of the word, it will have executed n-1 comparisons and push operations. Then, with the space it will execute PLUS n-1 pop operations and then the algorithm terminates. You see, it executed n-1 additional operations only when the space was found and not for each character read in the for loop.

So, in total, it will execute 2n operations and not n^2. This is valid for any combination of words and spaces. Therefore, the algorithm has complexity O(n).

Hope it is clear now.

Answer 2

Hi Bahubali,

If you do a careful analysis of your sortStack function you will see that the worse case of your sorting algorithm is actually when it is applied to an already sorted array.

The most expensive operations are carried in the nested loops as they transfer elements from one stack to another. The number of relocations will increase as the number of elements in the main stack decreases. You can verify that the number of relocations in the worse case follows an arithmetic progression which depends on n (number of elements).

Using big-O notation, the complexity of this algorithm is of order O(n^2), or quadratic, in the worse case.

You can verify this by drawing the steps when sorting for instance [1,2,3,4,5].

Answer 3

thank u so much sir

Answer 4

can u tell me time complexity of:(i think it should be o(n^2) because of while loop inside for loop
#include <bits/stdc++.h>
using namespace std;

void reverseWords(string str)
{
stack<char> st;

for (int i = 0; i < str.length(); ++i) {
if (str[i] != ' ')
st.push(str[i]);

else {
while (st.empty() == false) {
cout << st.top();
st.pop();
}
cout << " ";
}
}

while (st.empty() == false) {
cout << st.top();
st.pop();
}
}

int main()
{
string str = "Hello World";
reverseWords(str);
return 0;
}

Answer 5

Hi Bahubali,

Actually, the complexity is linear, or O(n).
Not always two nested loops indicates that the algorithm is quadratic. It all depends on the structure of these loops. You can verify that the second loop is just printing the word that was found.

Basically, to be quadratic as you thought, the second loop should be executed every time a new character is put on the stack. It is not the case. At most, this second loop is increasing the constant factor multiplying n.

Answer 6

sir I am confused
suppose str="Helloworld ";
has space at last after d character
now when it encounter space while loop run n-1 time where n is length of string and for loop has already run n-1
so why should it be O(n^2)?

Answer 7

omg now I understand thank u so much sir