question about code's time complexity

This is a discussion on question about code's time complexity within the C++ Programming forums, part of the General Programming Boards category; suppose that we have some while loop that runs at most n^2 times if the while loop runs only when ...

  1. #1
    nik
    nik is offline
    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
    682
    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).
    I never put signature, but I decided to make an exception.

  3. #3
    nik
    nik is offline
    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, 12:57 PM
  2. Using pointers
    By Big_0_72 in forum C Programming
    Replies: 3
    Last Post: 10-28-2008, 08:51 PM
  3. Sending an email in C program
    By Moony in forum C Programming
    Replies: 28
    Last Post: 10-19-2006, 11: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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21