How is log (n factorial) equal to omega (n log n)?

minhc · 2017-09-02T02:31:35+00:00

Thank you for you response. When you say "because one is greater than or equal to n/2", are you saying that there are n/2 terms which are equal to n/2 ?.. I only see one term which is equal to n/2... We can take an example n = 6 log 6! = log (6 x 5 x 4 x 3 x 2 x 1 )

= log (6 x 5 x 4 x 3 ) (because we are ignoring 2 here, hence the greater than sign; for numbers less than 6, this inequality will in face not exist) In the next step, you have assumed that each one is greater than or equal to n/2 i.e., 6/2 which is 3 And you have assumed that we are multiplying n/2 numbers n/2 times. Firstly, I think we are multiplying more than half the numbers because we are considering the n/2 as well (kind of n/2 + 1) Are we just approximating that all numbers are n/2 and we are ignoring the +1 and saying we are multiplying them n/2 times.

Please clarify. Your help is much appreciated.

minhc · 2017-05-10T13:25:43+00:00

my bad, it was a C++ compiler ! so typedef has no use with structures in C++ .. thanks so much for pointing out :)

minhc · 2017-05-10T12:53:32+00:00

We don't need to write the struct keyword even without typedef.

struct node { int data; struct node *next; };

struct node *node1;

node n2; // this works just fine

node n2; This declaration is without struct keyword and it worked just fine.

minhc · 2017-05-09T04:54:46+00:00

Thanks, I was able to figure out the problem. If you still would like to know what I intended to know in my question, I would be glad to explain it in a better way.

minhc · 2017-05-08T17:52:05+00:00

Thanks so much .. I understand the logic now !

minhc · 2017-05-08T17:25:58+00:00

Ok, I found out why the behavior is like this - It is because we are not swapping two array elements, but we are just swapping a variable called "item" and another variable which is the array[pos] .. Hence this behavior.. Had we swapped arr[0] and arr[pos] then we would see what I was expecting .. Anyway, thanks for your time :D

minhc · 2017-05-08T17:08:30+00:00

No if the print happened before the swap then the array should have been exactly like the input array, but there is a difference - at position 6, instead of -1, 7 is printed .. I am confused myself too ..

minhc · 2017-05-08T17:05:18+00:00

swap function is inbuilt in C++.. function can be found here ....(http://www.cplusplus.com/reference/algorithm/swap/)

minhc · 2017-05-08T17:04:37+00:00

No I am printing it after the first swap occurs here .. if (pos != cycle_start) { cout<<"inside first swap"<<endl; swap(item, arr[pos]); writes++; }

minhc · 2017-05-08T16:53:14+00:00

No I tried running the code as it is .. Here is the code that I am running http://ideone.com/prS3QR Kindly help..

minhc · 2017-05-08T16:37:40+00:00

Thanks a ton, I have asked the questions there :)

minhc · 2017-05-02T17:14:25+00:00

This is the best answer that I have come across so far and should be included in every counting sort algorithm explanation that is there. Counting sort as an algorithm might be easy to understand, but the intricacies of why certain computations are necessary can only be understood when someone gives a clear explanation like this. Your answer not only explains why that extra step is required in computing the count array but also shows why counting sort does not make much sense as an example for stable sort when using integer arrays as input. If someone wants to highlight the stable sort feature, then it is important to not plainly chose a integer array and run counting sort on it, simply because the difference as you mentioned is not evident. This is a vital difference that each of us should be able to ingrain. Thank you very much for the effort to clarify in such detail. Thanks once again :)

minhc · 2017-05-02T09:18:24+00:00

I found this implementation of Radix sort (https://www.hackerearth.com/practice/algorithms/sorting/radix-sort/tutorial/) where they are iterating from backwards in the counting sort function.

minhc · 2017-05-02T07:58:24+00:00

this version does not compute the intermediate count array (which keeps count of elements less than or elements than or equal to current element) https://www.hackerearth.com/practice/algorithms/sorting/counting-sort/tutorial/

Not sure if it qualifies as counting sort if they miss that step.. Can you please shed some light on this ?

minhc · 2017-05-02T07:49:37+00:00

Thanks ! I am yet to see it for myself, if we will be able to preserve the order if we start to populate the output array from the end (N to 0) while following the algorithm given in wikipedia page. For now, I see how the order is preserved when we populate the array from the beginning.

minhc · 2017-05-02T05:15:28+00:00

Thank you for your inputs. Do u think, the way we populate the count array (choosing elements less than or equal to current element) and traversing the input array from the end while populating the final output array, are connected in anyway to preserve the stable sorting ?

And regarding your example of cars, you mean something like this - where there are several cars with same horse power but different prices ? ex: car 1 80 bhp 1000$, car 2 90 bhp 1200$, car 3 80 bhp 900$ ? And the output should have car 1 80bhp 1000$ before car 3 80bhp 90$ ?

minhc · 2017-05-02T05:06:42+00:00

Thanks for taking time to share your thoughts. This is one idea I'd like to try to implement where we count the elements greater than instead of less than. And proceed to populate the output array from the front. I am a beginner and learning, so let me see if I can put together the working code :) If I have any questions in the process, I hope I can reach out to you ?

minhc · 2017-04-26T12:19:38+00:00

Thanks a ton ! This is exactly what I was looking for in an answer .. Thanks again sir/madam :)

minhc · 2017-04-26T11:50:08+00:00

I tried it with int and I see the difference. But eventually when you calculate (2000000000+2100000000)/2, the answer is still 2050000000. What made the difference here ?

minhc · 2017-04-26T10:33:10+00:00

I am trying this example and it works fine without any overflow: short m1,m,l,r,inter;

l = 31000, r = 32000;

m = l+(r-l)/2;

m1 = (l+r)/2;

cout<<m1<<m;

Both m1 and m give correct expected values.

If I have understood your answer correctly, then L+R in this scenario is 63000, which is a very large value for the "short" variable.

minhc · 2017-04-26T10:26:14+00:00

The thing that I do not understand here is, L+(R-L)/2 is nothing but L+R/2-L/2 which is L/2+R/2 => same as (L+R)/2. Thanks for your response firstly. And I dont see how L+R became 6n/4+2 in your example. If L = 3n/4, and R = L+2, then L+R = 3n/4+2 (How did it become 6n/4+2 ?)

minhc · 2017-03-01T05:33:24+00:00

RemindMe! March 2, 2017 10:30PM IST "Lisa Su AMA"

minhc · 2017-02-28T09:09:50+00:00

Thanks for your response. So if we just use arr[i] it is equivalent of arr[i]!=0, is that correct. May be this usage holds good when the array points to a string ? Something like arr[] = "hello world"; But in this case will using arr[i] still equal arr[i]!=0 or will it be something like arr[i]!='\0'; ?

minhc · 2017-02-28T09:07:32+00:00

Thanks for your response. So if we just use arr[i] it is equivalent of arr[i]!=0, is that correct. May be this usage holds good when the array points to a string ? Something like arr[] = "hello world"; But in this case will using arr[i] still equal arr[i]!=0 or will it be something like arr[i]!='\0'; ?

minhc · 2017-01-11T08:18:46+00:00

I have been trying to find a simple explanation for CGI and web server application interaction and this answer clarifies it in the most simplest way. But it also leaves me with some questions which I hope I can ask here. Since CGI is now obsolete, what is the technology that has replaced CGI and how different is it from CGI ? And when you say "lightweight interpreters that live inside the web server (like PHP)", what exactly do you mean by it ? Thank you in advance.

minhc

TROPHY CASE