Re: [algogeeks] BIG O
is O(long n!)
n! is O(n^n) by sterling approximation
hence it is O(log n^n) = O(nlogn)
On Sun, Oct 28, 2012 at 11:14 PM, Pralay Biswas
pralaybiswas2...@gmail.comwrote:
@ Siddharth :
Well, here is how you may understand it:
1) There is an outer loop that runs n times. (k)
2) Then there is an inner loop where j is initially set to current k, but
it halves itself in every iteration
-- So for example, if k is 32, and j halves every time, then the
inner loop runs for 5 times (32-16-8-4-2 etc)
-- This is a log base 2 order depreciation in for all k
3) So for every k, the inner loop runs for log k times. k itself varies
from 1 to n, hence O(nlogn)
Hope this helps.
#Pralay
MS-CS, UC Irvine
On Sun, Oct 28, 2012 at 10:38 AM, bharat b
bagana.bharatku...@gmail.comwrote:
while loop : logj base 2 ..
== log1 + log2 + ... logn = log(n!) [since logab = loga + logb]
== O(log(n^n)) = O(nlogn)
On Sun, Oct 28, 2012 at 3:56 AM, Siddharth Malhotra
codemalho...@gmail.com wrote:
Can somebody explain how it is O(n log n).
What is the significance of while loop in the above code?
I understand that the for loop implies O(n),does the log n in the O(n
log n) comes from the while loop?
What if there where two while loops in the for loop separately?
On Sat, Oct 27, 2012 at 3:26 AM, Pralay Biswas
pralaybiswas2...@gmail.com wrote:
Yes!
On Fri, Oct 26, 2012 at 2:55 PM, rahul sharma
rahul23111...@gmail.comwrote:
for k=1 to n
{
j=k;
while(j0)
j=j/2;
}
the complexity is big o is o(nlogn)
am i ryt
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
kriateive
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] AllBinomialCoefficients
use pascal's triangle -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Reading till EOF using cin
string str;
while(cin str)
{
cout str endl;
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] MICROSOFT WRITTEN QUESTION-2010
@bharat: When each step of nishant's algo is O(n) how can it sum up to O(nlogn)??? On Tue, Sep 13, 2011 at 9:18 AM, bharatkumar bagana bagana.bharatku...@gmail.com wrote: @nishant : your algo takes O(nlogn) time with higher constant behind this. can't we write better than this ? @sairam : will u pls provide implementation logic of u'r idea .. On Mon, Sep 12, 2011 at 12:43 PM, Sairam Ravu ravu...@gmail.com wrote: By merging smaller trees into larger trees we can obtain a much more efficient solution. -- With love and regards, Sairam Ravu I M. Tech(CS) Sri Sathya Sai Institute of Higher Learning To live life, you must think it, measure it, experiment with it, dance it, paint it, draw it, and calculate it -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **Please do not print this e-mail until urgent requirement. Go Green!! Save Papers = Save Trees *BharatKumar Bagana* **http://www.google.com/profiles/bagana.bharatkumarhttp://www.google.com/profiles/bagana.bharatkumar * Mobile +91 8056127652* bagana.bharatku...@gmail.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Algorithm to find two numbers in an array that sum up to a given number
With hashing.. make a hash table of elements from 0 to sum/2 if an element k is in sum/2 to sum then check if sum-k is in the hashtable. take care of the case when sum is even and sum/2 occurs only once. TC: O(n) Space complexity: O(sum) Method2: Sort the elements. Now maintain to pointers one at each end of the list and check their sum. Move the pointers towards each other depending on if their sum is greater than the required sum or less than it. TC: O(nlogn) SC: O(1) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] maximum XOR
@Neha take 42, 21 and 1 42 ^ 1 =43 while 42 ^21 =63 On Fri, Aug 26, 2011 at 10:28 PM, Neha Singh neha.ndelhi.1...@gmail.comwrote: Sort the nos., which can be done in O(nlogn) Now the 1st and the last integers are the required integers. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Jai Prakash Gupta Third Year Undergraduate Computer Science and Engineering Department IIT Kharagpur -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Square of Large integer
Hi hary, when do you think that there can be problem? The sq is never made to store a value 10^9 (for previous sq) +9*10^9 (for new sum) hence the sum never exceeds 10^10 which is under the range of int. Correct me if i go wrong somewhere. On Thu, Apr 28, 2011 at 12:26 PM, hary rathor harry.rat...@gmail.comwrote: bro u r currect but what happen when result exceed greater then integer range? here sq variable is not bery large -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] ThreeListSum
sort two of the list and pick one number in C(unsorted) to find if there exists a pair with the sum. This can be done in linear time by maintaining two pointers. Hence O(n^2). -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] amazon c questn
amazom needs 7*4=28 bytes -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: probability
@Dave: Sorry It was a typo but for the probability figures, When C shoots B then if he is successful then A will shoot C Hence he must be unsuccessful and then if B is unsuccessful then A must will Kill B and then C must kill A if B is successful then C must kill B now Hence P(when C shoots at B)=(2/3 )*( (1/2)*(1/3) + (1/2)*(1/3) ) =2/9 When C shoots at A i am similarly getting for the case when A is killed as 1/12 and when A is safe as 5/18 Hence total 13/36 where am i wrong? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] puzzle
@swayambhoo: ofcourse a cubical room must me symmetrical at allcorners, Hence, neway it will reach in min_dis=sqrt((4+3)^2+5^2)=8.6 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Find a specific number in a special matrix.
For n x m take first element of all the rows and insert in a min heap. Now take the smallest element and and if we have a track of from which row it belongs, we can take an element out of that row and insert in the heap. this will be done n x m times. Hence we have a time complexity of O(nmlog(m)) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: arrays
for each element in the second array apply binary search in first array. ie, For X[1] find 1 in first array with binary search. Time Complexity=O(nlogn) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: difference x
make another array(B) from (A) with all elements negated now find one element from B and one from A whose sum is x or -x. This can ofcourse be done in O(n). -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Valid Array
Algo: In first traverse find the min and the max values. if (max-min) not equals (N-1) return false In next traverse map each in a hashtable of size N where index=key-min. Now in case of collision return false return true -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: program for evaluation of remainders
rem=1; for(j=3;j=N+1;j++) rem=(rem*j)%n; return rem; -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: k nearest points
@coolfrog the question never asked u to find thm in order of thier distances. Correct me if i m wrong! find the distances in O(n) now using the partitioning process of quicksort. Dividing the array into two parts: Now if the Length of the first part is less than or equal to i we have to now make our search into one of the subarrays In average: T(n)=T(n/2)+O(n) which satisfies T(n)=O(n) though in worst case this algorithm can take u to O(n^2) but in average case it takes u to O(n) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] help me reduce the time limit
#includestdio.h
int main()
{
int arr[11]={0},sum2[1001]={0};
int type[1001]={0};//0 for tails
int N,Q,i,j,sum;
int a,b,c;
scanf(%d,N);
scanf(%d,Q);
for(i=0;iQ;i++)
{
scanf(%d%d%d,a,b,c);
if(a==0)
{
j=b;
int k=j/100;
while(j%100 j=c)
{
if(arr[j])
{
arr[j]=!arr[j];
sum2[k]--;
}
else{
arr[j]=!arr[j];
sum2[k]++;
}
j++;
}
while(j+100=c)
{
type[j/100]=!type[j/100];
j+=100;
}
k=j/100;
while(j=c)
{
if(arr[j])
{
arr[j]=!arr[j];
sum2[k]--;
}
else{
arr[j]=!arr[j];
sum2[k]++;
}
j++;
}
}
else{
sum=0;
j=b;
int k=j/100;
while(j%100 j=c)
{
sum+=arr[j]^type[k];
j++;
}
while(j+100=c)
{
if(type[j/100])
sum+=100-sum2[j/100];
else
sum+=sum2[j/100];
j+=100;
}
k=j/100;
while(j=c)
{
sum+=arr[j]^type[k];
j++;
}
printf(%d\n,sum);
}
}
return 0;
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Longest interval with maximum sum
@fenghuang: the last step will take O(n logn ) . Or there is some better way? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] k nearest points
will O(n) work or u wish something lesser dependent on k or log(n) ? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Learn
result=((n ((128)/3))1)|((n ((129)/3))1); -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
