Find First Free Position in Array in $O(\log n)$ Time Complexity

  • Context: MHB 
  • Thread starter Thread starter mathmari
  • Start date Start date
  • Tags Tags
    Position
Click For Summary
SUMMARY

The discussion centers on implementing a function to find the first free position in an array using a binary search algorithm with a time complexity of $O(\log n)$. The proposed function, FreePos(int *A, int low, int high), utilizes recursion to locate the first occurrence of INT_MAX in the array. Participants also discuss edge cases and potential segmentation faults when integrating this function into a larger system for merging two star systems, specifically addressing the handling of array bounds and ensuring proper indexing.

PREREQUISITES
  • Understanding of binary search algorithms
  • Familiarity with C programming and pointers
  • Knowledge of handling arrays and their bounds
  • Experience with recursion in programming
NEXT STEPS
  • Implement and test the FreePos function with various edge cases
  • Explore memory management techniques in C to prevent segmentation faults
  • Learn about the complexities of merging data structures in C
  • Study the implications of using INT_MAX as a sentinel value in arrays
USEFUL FOR

Software developers, particularly those working with C programming, data structure manipulation, and algorithm optimization, will benefit from this discussion.

mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :o

I want to merge two arrays.

How can I find the first free position of the first array in time complexity $O(\log n)$ ?? (Wondering)
 
Technology news on Phys.org
mathmari said:
Hey! :o

I want to merge two arrays.

How can I find the first free position of the first array in time complexity $O(\log n)$ ?? (Wondering)

Hi! (Smile)

How about a binary search? (Thinking)
 
I like Serena said:
Hi! (Smile)

How about a binary search? (Thinking)

I have done the following:

Code: 
int FreePos(int *A, int low, int high){
	int mid=low+floor((high-low)/2);
	if(high<low){
		return -1;
	}
	if(A[mid] == INT_MAX){
		if(A[mid-1] != INT_MAX){
			return mid -1;
		}
		else{
			FreePos(A, low, mid-2);
		}
	}
	else{
		if(A[mid+1] == INT_MAX){
			return mid;
		}
		else{
			FreePos(A, mid+2, high);
		}
	}
}

Is it correct?? (Wondering)I need this function for a function that combines two star systems, the "ss1" and "ss2".
The combination of the lists of the planetary systems should be done in time $O(1)$.
For the combination of the arrays of the free-floating planets we have to find the first free element of the first array, that should be done in time $O(\log n)$.
At the end the star system with identifier "ss2" should be deleted from the array of star systems, and at the position of the deleted star system we insert the star system that is at the last position of the array.

I have done the following:

Code: 
int SolarSystem_Combiner(int ss1, int ss2){
	int i, k, m, pos1, pos2;
	for(i=0; i<Sfreep; i++){
			if(StarS[i].ss1==ss1){
				k=i;
				
			}
	}
	for(i=0; i<Sfreep; i++){
			if(StarS[i].ss2==ss2){
				m=i;
				
			}
	}
	

	StarS[k].Sentinel->next=StarS[m].plasy;
	StarS[k].Sentinel=StarS[m].Sentinel;
	

	pos1=FreePos(StarS[k].ffplan, 0, max);
	pos2=FreePos(StarS[m].ffplan, 0, max);
	for(i=0; i<pos2; i++){
		StarS[k].ffplan[pos+i]=StarS[m].ffplan[i];
	}
	
	
	
	
	return 0;
}

Is it correct?? (Wondering)

How can I delete the star system with identifier "ss2" from the array of star systems?? (Wondering)
 
mathmari said:
Code: 
int FreePos(int *A, int low, int high){
	int mid=low+floor((high-low)/2);
	if(high<low){
		return -1;
	}
	if(A[mid] == INT_MAX){
		if(A[mid-1] != INT_MAX){
			return mid -1;
		}
		else{
			FreePos(A, low, mid-2);
		}
	}
	else{
		if(A[mid+1] == INT_MAX){
			return mid;
		}
		else{
			FreePos(A, mid+2, high);
		}
	}
}

Let's check a couple of edge cases. (Nerd)

What would you get in each of the following cases:
Code: 
int A[1] = {1};                FreePos(A, 0, 0);
int B[1] = {INT_MAX};          FreePos(B, 0, 0);
int C[2] = {1, 2};             FreePos(C, 0, 1);
int D[2] = {INT_MAX, INT_MAX}; FreePos(D, 0, 1);
(Wondering)
 
I like Serena said:
Let's check a couple of edge cases. (Nerd)

What would you get in each of the following cases:
Code: 
int A[1] = {1};                FreePos(A, 0, 0);
int B[1] = {INT_MAX};          FreePos(B, 0, 0);
int C[2] = {1, 2};             FreePos(C, 0, 1);
int D[2] = {INT_MAX, INT_MAX}; FreePos(D, 0, 1);
(Wondering)

I made some changes...

Code: 
int FreePos(int *A, int low, int high){
	int mid=low+floor((high-low)/2);
	if(high<low){
		return -1;
	}
	if(low==high){
		if(A[low] == INT_MAX){
			return low;
		}
		else{
			return low+1;
		}
	}
	else if(A[mid] == INT_MAX && mid-1>=low){
		if(A[mid-1] != INT_MAX){
			return mid -1;
		}
		else{
			if(mid-2 >= low){
				FreePos(A, low, mid-2);
			}
			else{
				return mid-2;
			}
		}
	}
	else if(A[mid] != INT_MAX && mid+1<=high){
		if(A[mid+1] == INT_MAX){
			return mid;
		}
		else{
			if(mid+2 <= high){
				FreePos(A, mid+2, high);
			}
			else{
				return mid+2;
			}
		}
	}
}

Is it better now?? (Wondering)
 
mathmari said:
I made some changes...

Code: 
int FreePos(int *A, int low, int high){
	int mid=low+floor((high-low)/2);
	if(high<low){
		return -1;
	}
	if(low==high){
		if(A[low] == INT_MAX){
			return low;
		}
		else{
			return low+1;
		}
	}
	else if(A[mid] == INT_MAX && mid-1>=low){
		if(A[mid-1] != INT_MAX){
			return mid -1;
		}
		else{
			if(mid-2 >= low){
				FreePos(A, low, mid-2);
			}
			else{
				return mid-2;
			}
		}
	}
	else if(A[mid] != INT_MAX && mid+1<=high){
		if(A[mid+1] == INT_MAX){
			return mid;
		}
		else{
			if(mid+2 <= high){
				FreePos(A, mid+2, high);
			}
			else{
				return mid+2;
			}
		}
	}
}

Is it better now?? (Wondering)

How about:
Code: 
int E[] = {INT_MAX, INT_MAX, INT_MAX};
(Wondering)

As a suggestion, perhaps remove all if statements from the recursive cases? (Wasntme)
 
I like Serena said:
How about:
Code: 
int E[] = {INT_MAX, INT_MAX, INT_MAX};
(Wondering)

As a suggestion, perhaps remove all if statements from the recursive cases? (Wasntme)

I tried it again...

Code: 
int FreePos(int *A, int low, int high){
	int mid=low+floor((high-low)/2);
	if(high<low){
		return -1;
	}
	if(A[0] == INT_MAX){
		return 0;
	}
	if(A[high] < INT_MAX){
		return high+1;
	}
	if(A[mid] < INT_MAX){
		if(A[mid+1] == INT_MAX){
			return mid+1;
		}
		else{
			return FreePos(A,  mid+2, high);
		}
	}
	else{
		if(A[mid-1] < INT_MAX){
			return mid-1;
		}
		else{
			return FreePos(A, low, mid-2);
		}
	}		
}

Is it better now?? (Wondering)
 
mathmari said:
I tried it again...

Code: 
int FreePos(int *A, int low, int high){
	int mid=low+floor((high-low)/2);
	if(high<low){
		return -1;
	}
	if(A[0] == INT_MAX){
		return 0;
	}
	if(A[high] < INT_MAX){
		return high+1;
	}
	if(A[mid] < INT_MAX){
		if(A[mid+1] == INT_MAX){
			return mid+1;
		}
		else{
			return FreePos(A,  mid+2, high);
		}
	}
	else{
		if(A[mid-1] < INT_MAX){
			return mid-1;
		}
		else{
			return FreePos(A, low, mid-2);
		}
	}		
}

Is it better now?? (Wondering)

I'm afraid that the way you had it, you did need those extra if conditions.
Otherwise you'll be accessing the array outside of its bounds, which would cause a segmentation violation. (Worried)

I'm suggesting something more like this:
Code: 
int FreePos(int *A, int low, int high){
	int mid=low+floor((high-low)/2);

	<Final cases>

	if(A[mid] == INT_MAX){
		return FreePos(A, low, mid);
	}
	else{
		return FreePos(A,  mid+1, high);
	}		
}
(Thinking)
 
I like Serena said:
I'm afraid that the way you had it, you did need those extra if conditions.
Otherwise you'll be accessing the array outside of its bounds, which would cause a segmentation violation. (Worried)

I'm suggesting something more like this:
Code: 
int FreePos(int *A, int low, int high){
	int mid=low+floor((high-low)/2);

	<Final cases>

	if(A[mid] == INT_MAX){
		return FreePos(A, low, mid);
	}
	else{
		return FreePos(A,  mid+1, high);
	}		
}
(Thinking)

Is the final case when we have an array with only one element, and we have to check if it is INT_MAX or not?? (Wondering)
 
  • #10
mathmari said:
Is the final case when we have an array with only one element, and we have to check if it is INT_MAX or not?? (Wondering)

Yes! (Nod)

The case [m]high < low[/m] should not even occur, although it won't hurt to handle it anyway.
 
  • #11
I like Serena said:
Yes! (Nod)

The case [m]high < low[/m] should not even occur, although it won't hurt to handle it anyway.

So, should it be as followed??

Code: 
int FreePos(int *A, int low, int high){
	int mid=low+floor((high-low)/2);
	
	if(high<low){
		return -1;
	}
	
	if(low == high){
		if(A[low] == INT_MAX){
			return low;
		}
		else{
			printf("There is no free position.\n");
			return -1;
		}
	}

	if(A[mid] == INT_MAX){
		return FreePos(A, low, mid);
	}
	else{
		return FreePos(A,  mid+1, high);
	}		
}

(Wondering)
 
  • #12
mathmari said:
So, should it be as followed??

Code: 
int FreePos(int *A, int low, int high){
	int mid=low+floor((high-low)/2);
	
	if(high<low){
		return -1;
	}
	
	if(low == high){
		if(A[low] == INT_MAX){
			return low;
		}
		else{
			printf("There is no free position.\n");
			return -1;
		}
	}

	if(A[mid] == INT_MAX){
		return FreePos(A, low, mid);
	}
	else{
		return FreePos(A,  mid+1, high);
	}		
}

(Wondering)

Almost. (Thinking)

Remember that the range low to high is a sub range in the actual array.
If, in the final case, A[low] != INT_MAX, it means that the first free element comes after.
And if the array is completely full, the function will return the index after the last valid one.

It is good programming practice to document this behavior in comments above the function. And when we call the function, we need to ensure that case is handled. (Nerd)
 
  • #13
I like Serena said:
Remember that the range low to high is a sub range in the actual array.
If, in the final case, A[low] != INT_MAX, it means that the first free element comes after.
And if the array is completely full, the function will return the index after the last valid one.

Do you mean that I should do it as followed??

Code: 
int FreePos(int *A, int low, int high){
	int mid=low+floor((high-low)/2);
	
	if(high<low){
		return -1;
	}
	
	if(low == high){
		if(A[low] == INT_MAX){
			return low;
		}
		else{
			return low+1;
		}
	}

	if(A[mid] == INT_MAX){
		return FreePos(A, low, mid);
	}
	else{
		return FreePos(A,  mid+1, high);
	}		
}

(Wondering)
 
  • #14
mathmari said:
Do you mean that I should do it as followed??

Code: 
int FreePos(int *A, int low, int high){
	int mid=low+floor((high-low)/2);
	
	if(high<low){
		return -1;
	}
	
	if(low == high){
		if(A[low] == INT_MAX){
			return low;
		}
		else{
			return low+1;
		}
	}

	if(A[mid] == INT_MAX){
		return FreePos(A, low, mid);
	}
	else{
		return FreePos(A,  mid+1, high);
	}		
}

(Wondering)

Yep! (Smile)
 
  • #15
I like Serena said:
Yep! (Smile)

Great! (Yes)
mathmari said:
I need this function for a function that combines two star systems, the "ss1" and "ss2".
The combination of the lists of the planetary systems should be done in time $O(1)$.
For the combination of the arrays of the free-floating planets we have to find the first free element of the first array, that should be done in time $O(\log n)$.
At the end the star system with identifier "ss2" should be deleted from the array of star systems, and at the position of the deleted star system we insert the star system that is at the last position of the array.

I have written a function for the combination of the two star systems.

When I call the function FreePos() as followed:

[m]pos=FreePos(StarS[k].ffplan, 0, max);[/m]

I get a segmentation fault because of the first argument of the function.

What should I change?? (Wondering)
 
  • #16
mathmari said:
I have written a function for the combination of the two star systems.

When I call the function FreePos() as followed:

[m]pos=FreePos(StarS[k].ffplan, 0, max);[/m]

I get a segmentation fault because of the first argument of the function.

What should I change?? (Wondering)

I you get a segmentation fault, it means one (or more) of the following:
  1. k is out of range to index StarS,
  2. ffplan does not behave like an array,
  3. ffplan is an array, but it does not have (max - 0 + 1) elements,
  4. there is still a mistake in the code of Freepos.
How can we eliminate each of these possibilities? (Thinking)
 
  • #17
I like Serena said:
I you get a segmentation fault, it means one (or more) of the following:
  1. k is out of range to index StarS,
  2. ffplan does not behave like an array,
  3. ffplan is an array, but it does not have (max - 0 + 1) elements,
  4. there is still a mistake in the code of Freepos.
How can we eliminate each of these possibilities? (Thinking)

  1. I found k as followed:

    Code: 
    for(i=0; i<Sfreep; i++){
			if(StarS[i].ss==ss1){
				k=i;
				
			}
	}

    So, k is not out of range to index StarS, right?? (Wondering)
  2. The definition of ffplan is:

    Code: 
    struct starsy { 
 int ss;               /*Identifier of the star system*/
 plansys_t *plasy;     /*Pointer to the first element in the list of the planetary system */
 ffplan_t ffplan[max];     /*The array of the free-floating planets */
 plansys_t *Sentinel;      /*Pointer to the sentinel node of the list of the planetary system */
};

    So, isn't it an array?? (wondering)
  3. How can I check that?? (Wondering)
  4. (Worried)(Sweating)
 
  • #18
mathmari said:
So, k is not out of range to index StarS, right?? (Wondering)

[m]k[/m] is guaranteed to be in range if [m]Sfreep[/m] is.
How can you tell that it is? (Wondering)
[*]The definition of ffplan is:

Code: 
struct starsy { 
 int ss;               /*Identifier of the star system*/
 plansys_t *plasy;     /*Pointer to the first element in the list of the planetary system */
 ffplan_t ffplan[max];     /*The array of the free-floating planets */
 plansys_t *Sentinel;      /*Pointer to the sentinel node of the list of the planetary system */
};

So, isn't it an array?? (wondering)

Check! $\checkmark$
[*]How can I check that?? (Wondering)

Well, the algorithm (as it is now) expects [m]high[/m] to be the highest valid index in the array.
... but [m]max[/m] is not a valid index in the array, it is one higher.
So this might cause a segmentation fault.
Either we have to adapt the algorithm, or we have to pass [m]max - 1[/m].
[*](Worried)(Sweating)

The way to do it, is to test the function against a series of boundary conditions.
Like:
Code: 
int main() {
  assert(-1 == FreePos(NULL, 0, -1));
  int A[1] = {1};
  assert(1 == FreePos(A, 0, 0));
  int B[1] = {INT_MAX};
  assert(0 == FreePos(B, 0, 0));
  int C[2] = {1, 2};
  assert(2 == FreePos(C, 0, 1));
  int D[2] = {1, INT_MAX};
  assert(1 == FreePos(D, 0, 1));
  int E[2] = {INT_MAX, INT_MAX};
  assert(0 == FreePos(E, 0, 1));
  int F[3] = {INT_MAX, INT_MAX, INT_MAX};
  assert(0 == FreePos(F, 0, 2));
  int G[3] = {1, INT_MAX, INT_MAX};
  assert(1 == FreePos(G, 0, 2));
  int H[3] = {1, 2, 3};
  assert(3 == FreePos(H, 0, 2));
  return 0;
}

Can this code compile and run successfully? (Wondering)
This is called "unit testing".

Alternatively, you could print all the elements in ffplan beforehand.
Then figure out for yourself what the return value of FreePos() should be.
And perhaps print a couple of intermediate results in FreePos() to verify if it runs as you expect.
This is called "debugging". (Nerd)
 
  • #19
I like Serena said:
[m]k[/m] is guaranteed to be in range if [m]Sfreep[/m] is.
How can you tell that it is? (Wondering)

I added an if statement at the following function:

Code: 
int Constitution(int ss) {
        int i;

        starsy_t *starsystem = &StarS[Sfreep];
        Sfreep++;
		
        if(Sfreep>N){
	        return -1;
        }

        starsystem->ss = ss;
        starsystem->plasy=starsystem->Sentinel;
	for(i=0; i<max; i++){
		starsystem->ffplan[i].fp=INT_MAX;
		starsystem->ffplan[i].ff=NULL;
	}

	return (Sfreep - 1);
}

Now, [m]Sfreep[/m] is guaranteed to be in range, right?? (Wondering)

I like Serena said:
Well, the algorithm (as it is now) expects [m]high[/m] to be the highest valid index in the array.
... but [m]max[/m] is not a valid index in the array, it is one higher.
So this might cause a segmentation fault.
Either we have to adapt the algorithm, or we have to pass [m]max - 1[/m].

You're right!

I changed that, and now I call the function as followed:

[m]pos=FreePos(StarS[k].ffplan, 0, max-1);[/m]

But, I still get the following error:

[m]warning: passing arg 1 of 'FreePos' from incompatible pointer type[/m]
I like Serena said:
The way to do it, is to test the function against a series of boundary conditions.
Like:
Code: 
int main() {
  assert(-1 == FreePos(NULL, 0, -1));
  int A[1] = {1};
  assert(1 == FreePos(A, 0, 0));
  int B[1] = {INT_MAX};
  assert(0 == FreePos(B, 0, 0));
  int C[2] = {1, 2};
  assert(2 == FreePos(C, 0, 1));
  int D[2] = {1, INT_MAX};
  assert(1 == FreePos(D, 0, 1));
  int E[2] = {INT_MAX, INT_MAX};
  assert(0 == FreePos(E, 0, 1));
  int F[3] = {INT_MAX, INT_MAX, INT_MAX};
  assert(0 == FreePos(F, 0, 2));
  int G[3] = {1, INT_MAX, INT_MAX};
  assert(1 == FreePos(G, 0, 2));
  int H[3] = {1, 2, 3};
  assert(3 == FreePos(H, 0, 2));
  return 0;
}

Can this code compile and run successfully? (Wondering)
This is called "unit testing".

I ran the program and the result are the correct ones! (Emo)
 
  • #20
Hi,
The following version of binary search is nothing new, but it does do exactly what you want. It returns the index of the first occurrence of the search argument. If you're up to it, you might try and prove the correctness of the algorithm. Also you might try to modify the function so that the return is the last occurrence of the search argument.

Code: 
/* Upon entry the array a of n components is sorted.  x is a search
   argument.  If x occurs as a component of the array, the return is the
   FIRST index i with a[i]==x; i.e. for j<i, a[j]!=x.  If x is not a
   componet, return is -1.
*/
int binarySearch(int *a,int n,int x) {
    int lo=0,hi=n-1,mid;
    while (lo<hi) {
        mid=(lo+hi)/2; // in C, this is floor(a+b/2)
        if (a[mid]<x) {
            lo=mid+1;
        }
        else {
            hi=mid;
        }
    }
    if (a[hi]==x){
        return(lo);
    }
    else {
        return(-1);
    }
}
 
  • #21
mathmari said:
I added an if statement at the following function:

Code: 
int Constitution(int ss) {
        int i;

        starsy_t *starsystem = &StarS[Sfreep];
        Sfreep++;
		
        if(Sfreep>N){
	        return -1;
        }

        starsystem->ss = ss;
        starsystem->plasy=starsystem->Sentinel;
	for(i=0; i<max; i++){
		starsystem->ffplan[i].fp=INT_MAX;
		starsystem->ffplan[i].ff=NULL;
	}

	return (Sfreep - 1);
}

Now, [m]Sfreep[/m] is guaranteed to be in range, right?? (Wondering)

Whether it fits or not, [m]Sfreep[/m] is still incremented, isn't it? (Wondering)
So no, I don't think it is guaranteed to be in range.

[m]warning: passing arg 1 of 'FreePos' from incompatible pointer type[/m]

Aaaah.
Argument 1 of FreePos() is an [m]int*[/m], and you're passing a [m]ffplan_t*[/m] and they do not match.
What happens if you change the type? (Wondering)
I ran the program and the result are the correct ones! (Emo)

Nice! (Smile)
 
  • #22
I like Serena said:
Whether it fits or not, [m]Sfreep[/m] is still incremented, isn't it? (Wondering)
So no, I don't think it is guaranteed to be in range.

What can I do so that it is guaranteed to be in range?? (Wondering)
I like Serena said:
Aaaah.
Argument 1 of FreePos() is an [m]int*[/m], and your passing a [m]ffplan_t*[/m] and they do not match.
What happens if you change the type? (Wondering)

I changed it, and I changed [m]A[low][/m] to [m]A[low].fp[/m].

Now, there is no segmentation fault! (Party)
 
  • #23
mathmari said:
What can I do so that it is guaranteed to be in range?? (Wondering)

Only increment Sfreep if Sfreep < N.
Then, after a failure to add a new star system, Sfreep will still be N.
I changed it, and I changed [m]A[low][/m] to [m]A[low].fp[/m].

Now, there is no segmentation fault! (Party)

(drink)
 
  • #24
I like Serena said:
Only increment Sfreep if Sfreep < N.
Then, after a failure to add a new star system, Sfreep will still be N.

Do you mean that it should be as followed??

Code: 
int Constitution(int ss) {
        int i;

        while(Sfreep<N){
        	starsy_t *starsystem = &StarS[Sfreep];
        	Sfreep++;
		}

        starsystem->ss = ss;
        starsystem->plasy=starsystem->Sentinel;
	for(i=0; i<max; i++){
		starsystem->ffplan[i].fp=INT_MAX;
		starsystem->ffplan[i].ff=NULL;
	}

	return (Sfreep - 1);
}

(Wondering)
 
  • #25
mathmari said:
Do you mean that it should be as followed??

Code: 
int Constitution(int ss) {
        int i;

        while(Sfreep<N){
        	starsy_t *starsystem = &StarS[Sfreep];
        	Sfreep++;
		}

        starsystem->ss = ss;
        starsystem->plasy=starsystem->Sentinel;
	for(i=0; i<max; i++){
		starsystem->ffplan[i].fp=INT_MAX;
		starsystem->ffplan[i].ff=NULL;
	}

	return (Sfreep - 1);
}

(Wondering)

That should be an "if" instead of a "while".
And if there is no more space, the function should return immediately. (Worried)
 
  • #26
I like Serena said:
That should be an "if" instead of a "while".
And if there is no more space, the function should return immediately. (Worried)

So should it be as followed??

Code: 
if(Sfreep<N){
        	starsy_t *starsystem = &StarS[Sfreep];
        	Sfreep++;
		}
		
		if(Sfreep>=N){
			exit();
		}

(Wondering)
 
  • #27
mathmari said:
So should it be as followed??

Code: 
if(Sfreep<N){
        	starsy_t *starsystem = &StarS[Sfreep];
        	Sfreep++;
		}
		
		if(Sfreep>=N){
			exit();
		}

(Wondering)

Something like that.
Does it compile? (Wondering)
 
  • #28
I like Serena said:
Something like that.
Does it compile? (Wondering)

No, I get the following error:

[m]error: `starsystem' undeclared (first use in this function)[/m](Wondering)
 
  • #29
mathmari said:
No, I get the following error:

[m]error: `starsystem' undeclared (first use in this function)[/m](Wondering)

What do you think is wrong? (Thinking)
 
  • #30
I like Serena said:
What do you think is wrong? (Thinking)

Should I declare [m]starsystem[/m] outside the if?? (Wondering)
 

Similar threads

Time complexity of a binary search
  • · Replies 12 ·
Replies
12
Views
2K
I don't understand my prof's notes relating to time complexity
  • · Replies 7 ·
Replies
7
Views
2K
Prime Number Detection: Running Time of Algorithm
  • · Replies 4 ·
Replies
4
Views
2K
What is the Most Efficient Algorithm for Finding Duplicates in an Array?
  • · Replies 12 ·
Replies
12
Views
3K
MHB Why Use a Helper Variable When Inserting an Element in an Array?
  • · Replies 98 ·
4
Replies
98
Views
14K
MHB How to Sort Elements of a Matrix in O(n) Time Complexity?
  • · Replies 1 ·
Replies
1
Views
2K
MHB Find Elements of Array w/ Quotient = y: O(m log m)
  • · Replies 20 ·
Replies
20
Views
4K
MHB Dynamic programming: which recurrence relation do we use?
  • · Replies 2 ·
Replies
2
Views
2K
MHB Constructing a Star System with O(1) Complexity
  • · Replies 20 ·
Replies
20
Views
5K
Complexity of this heap algorithm
  • · Replies 1 ·
Replies
1
Views
2K