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

  • MHB
  • Thread starter mathmari
  • Start date
  • Tags
    Position
In summary: Yes, that would be one of the final cases. We also need to check if the first or last element of the array is INT_MAX, and handle those cases accordingly. (Nerd)In summary, we discussed different ways to find the first free position in an array in time complexity O(log n). We also explored edge cases and made suggestions for improvements to the code.
  • #1
mathmari
Gold Member
MHB
5,049
7
Hey! :eek:

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
  • #2
mathmari said:
Hey! :eek:

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)
 
  • #3
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)
 
  • #4
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)
 
  • #5
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)
 
  • #6
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)
 
  • #7
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)
 
  • #8
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)
 
  • #9
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++;
		
        [COLOR="#FF0000"]if(Sfreep>N){
	        return -1;
        }[/COLOR]

        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++;
		
        [COLOR="#FF0000"]if(Sfreep>N){
	        return -1;
        }[/COLOR]

        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)
 
  • #31
mathmari said:
Should I declare [m]starsystem[/m] outside the if?? (Wondering)

The would help yes.
The life time of an object ends when we get to the matching closing brace. (Nerd)
 
  • #32
I like Serena said:
The life time of an object ends when we get to the matching closing brace. (Nerd)

What do you mean?? (Wondering)
 
  • #33
mathmari said:
What do you mean?? (Wondering)

When you have:
Code: 
void function()
{
  int a = 2;
  {
    int a = 3;
    printf("%d\n", a);
  }
  printf("%d\n", a);
}
what do you think gets printed? (Wondering)
 
  • #34
I like Serena said:
When you have:
Code: 
void function()
{
  int a = 2;
  {
    int a = 3;
    printf("%d\n", a);
  }
  printf("%d\n", a);
}
what do you think gets printed? (Wondering)

It will print:

3
2

right?? (Wondering)
 
  • #35
mathmari said:
It will print:

3
2

right?? (Wondering)

Yep. (Nod)

When "int a = 3" is declared, local stack memory is allocated for it.
Furthermore it "hides" the "a" that was declared earlier.
When the closing brace comes by, the local stack memory is automatically released.
Afterwards, the original "a" becomes visible again. (Nerd)
 

Similar threads

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

Hot Threads

Recent Insights

Back
Top