Thread: is it log(n) ??

  1. #1
    Registered User noririco's Avatar
    Join Date
    Nov 2013
    Posts
    90

    is it log(n) ??

    Code:
    #include <stdio.h>
    
    int max(int arr[],int n) {
    
    
    	int max=0;
    	int t;
    
    
    	for (t=1;t<=n;t++)
    	{
    		if (arr[t-1]==0) 
    		{
    			if (t==1) return 0; // arr = {0}
    
    
    			max = arr[t-2];
    		    break;  
    		}
    	max = arr[n-1]; // none of arr elements are 0 case
    	}
    	 
    	
    	return max;
    
    
    }
    
    
    int main () {
    
    
    	int arr[]={1,2,2,3,5,0,0,0};
    	int n = sizeof(arr)/sizeof(arr[0]);
    	
    	printf("%d\n", max(arr,n));
    
    
    	return 0;
    }

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    I suppose that depends a bit on how you define "n" -- if n is the number of actual data points (as opposed to the "fake" 0 data points on the end), then you go through the loop n+1 times, so you are looking at O(n). If you take "n" to mean the size of the array including the fake 0s at the end, then the average/amortized case would depend on how full the array tends to be, but the worst case would again have to be O(n).

  3. #3
    Registered User noririco's Avatar
    Join Date
    Nov 2013
    Posts
    90
    i cant send msg ? it tells me
    The following errors occurred with your submission


    1. Please use code tags: insert
      Code:
       before your source code and
      after it in order to post. See Posting Code - Read this First for more information.



    and I didnt post a code.

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by noririco View Post
    i cant send msg ? it tells me
    The following errors occurred with your submission


    1. Please use code tags: insert
      Code:
       before your source code and
      after it in order to post. See Posting Code - Read this First for more information.



    and I didnt post a code.
    The forum software assumes that you would never want to use these characters (there might be more but these are the ones I know about) in ordinary English, and therefore insists they be enclosed in code tags:
    Code:
    {
    }
    So don't use those symbols.

Popular pages Recent additions subscribe to a feed