How to determine the best case and worst case of an program(algorithm)?

Posted by college_stud on Stack Overflow See other posts from Stack Overflow or by college_stud
Published on 2010-04-19T13:20:22Z Indexed on 2010/04/19 13:23 UTC
Read the original article Hit count: 187

Filed under:

worst-case

|

function

|

algorithm

|

mathematics

|

programming-languages

Suppose I have this program, I want to compare 2 input lists. Assume array A and array B. How do I determine the best case and worst case of the function?

Here is my code in [php]:

foreach($array_1 as $k){
    if(!in_array($k, $array_2)){
        array_push($array_2, $k);
    }
}

What is the best case and worst case of the for loop? Please include some explaination, thank you :)

© Stack Overflow or respective owner

Related posts about worst-case

How to determine the best case and worst case of an program(algorithm)?

as seen on Stack Overflow - Search for 'Stack Overflow'
Suppose I have this program, I want to compare 2 input lists. Assume array A and array B. How do I determine the best case and worst case of the function? Here is my code in [php]: foreach($array_1 as $k){ if(!in_array($k, $array_2)){ array_push($array_2, $k); } } What is the… >>> More
Web Security: Worst-Case Situation

as seen on Stack Overflow - Search for 'Stack Overflow'
I currently have built a system that checks user IP, browser, and a random-string cookie to determine if he is an admin. In the worst case, someone steals my cookie, uses the same browser I do, and masks his IP to appear as mine. Is there another layer of security I should add onto my script to make… >>> More
Search Complexity of a Hashtable within a Hashtable?

as seen on Stack Overflow - Search for 'Stack Overflow'
Say we have a hashtable of size m, and at each bucket we store a hashtable of size p. What would the worst case/average case search complexity be? I am inclined to say that since computing a hash function is still atomic, the only worst case scenario is if the value is at the end of the linked list… >>> More
Efficient algorithm to find first available name

as seen on Stack Overflow - Search for 'Stack Overflow'
I have an array containing names of items. I want to give the user the option to create items without specifying their name, so my program will have to supply a unique default name, like "Item 1". The challenge is that the name has to be unique so i have to check all the array for that default name… >>> More
Worse is better. Is there an example?

as seen on Stack Overflow - Search for 'Stack Overflow'
Is there a widely-used algorithm that has time complexity worse than that of another known algorithm but it is a better choice in all practical situations (worse complexity but better otherwise)? An acceptable answer might be in a form: There are algorithms A and B that have O(N**2) and O(N)… >>> More

Related posts about function

MAMP + Python MySQLDB - trouble installing

as seen on Server Fault - Search for 'Server Fault'
I'm currently running the latest version of MAMP on my Snow Leopard OSX, and I'm trying to install MySQLDB. Downloaded: MySQL-python-1.2.3c1 I went into the setup_posix.py and adjusted the location of the mysql_config to the one in MAMP: mysql_config.path = "/Applications/MAMP/Library/bin/mysql_config" When… >>> More
Compiling a program with a legacy version of gcc

as seen on Stack Overflow - Search for 'Stack Overflow'
This is probably a very difficult problem to troubleshoot with the information I can practically provide, but I'm hoping someone might be able to at least point me in a possible direction. I'm trying to install HTK (http://htk.eng.cam.ac.uk/), which, according to this page needs to be installed using… >>> More
eventmachine on debian fails install via rubygems

as seen on Stack Overflow - Search for 'Stack Overflow'
this has been killing me for the last 5 hours. I don't seem to be able to get eventmachine running on my debian box. here this output: $ gem install thin Building native extensions. This could take a while... ERROR: Error installing thin: ERROR: Failed to build gem native extension. … >>> More
Can overloading is possible with two version of function, constant member function and function with

as seen on Stack Overflow - Search for 'Stack Overflow'
Hello, I just came across various overloading methods like type of parameter passed, varying number of parameters, return type etc. I just want to know that can I overload a function with following two version //function which can modify member String& MyClass::doSomething(); //constant member… >>> More
[PHP] function().function() VS function()function()

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi all, I was writing a foreach Loop in PHP5. Here is the script: foreach(range('A','Z') as $char) // line 1 { // line 2 echo strtoupper($char)strtolower($char); // line 3 } // line 4 And I got this error message Parse error: parse error, unexpected T_STRING in testing.php on line 3 I spent almost… >>> More