Thread: question about code's time complexity

  1. #1
    Registered User
    Join Date
    Nov 2010
    Posts
    44

    question about code's time complexity

    suppose that we have some while loop that runs at most n^2 times

    if the while loop runs only when an element exists in an array(you have to find the element and it's index) then does that mean that the complexity is O(n^3)?

    Code:
    bool find(int &i, array){
     
        int j;
        for(j=0;j<size_of_array;j++){
              if(array[j] == something) {
                            i = j;
                            break;
    
                }
    
    }
    
    
     
    
    int main(void) {
    
    
     ... 
      
     while(find(...)){
    
               run n^2 times
    
            }
    
    }
    thanks in advance

  2. #2
    Registered User
    Join Date
    Aug 2010
    Location
    Poland
    Posts
    733
    O(n^2) is multiplied by the time spent on finding element. You can check this in O(log n) or even O(1). Yes, in your case, it is O(n^3).

  3. #3
    Registered User
    Join Date
    Nov 2010
    Posts
    44
    thanks kmdv

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. question about time conversion
    By jeremy_a08 in forum C++ Programming
    Replies: 1
    Last Post: 10-26-2010, 11:57 AM
  2. Using pointers
    By Big_0_72 in forum C Programming
    Replies: 3
    Last Post: 10-28-2008, 07:51 PM
  3. Sending an email in C program
    By Moony in forum C Programming
    Replies: 28
    Last Post: 10-19-2006, 10:42 AM
  4. time question.
    By InvariantLoop in forum C Programming
    Replies: 5
    Last Post: 02-01-2005, 02:00 PM
  5. inputting time in separate compilation
    By sameintheend01 in forum C++ Programming
    Replies: 6
    Last Post: 03-13-2003, 04:33 AM