Runtime Analysis (Again)

From the first slide, the second one is faster, since it goes from the correct positions faster than using two loops.


Variety of solutions, with pros and cons, like Running time and Space Usage.


Generally find the fastest solution, except for a space concern.


Runtime can’t just be based on seconds, since every computer is different.


Three perspectives to analyze code.


Best Case

  • Don’t always argue/assume the input the size of data! Becomes worst-case.

  • Always assume an arbitrarily large input, and find the best possible time for it.

Average Case

  • Common to observe, and randomly drawn from a given distribution

Worst Case

  • Absolute worst, and very common for theoretical computer scientist to study.


For binary search


Best: O(1)

Average: O(n/2)

Worst: O(n)

(another case where a function isn’t related with input size is when there is no parameters of the function)


With log n, it increases very slowly, so with the log of the number is the time in seconds/speed.


If n! covers everything, why not always use it?

Since O(n!) isn’t much information, as well as it’s really long, compared to the rest, and while n! might be the worst/ most applicable for each, not exact enought.


It isn’t informative, in a way when it comes to runtime, it can apply to everything, like how for guessing a number, one clue can be way more precise than the other.

Just multiplying the row# and col#.




For slide 14, the best case is when all elements are odd, since when it is odd, it won’t need to check more than n times.


With the code, while it might check n times, it won’t have to repeat the entire thing.


When everything is even, it would need to check O(n²) times.


For the average case, when it is a mix of odd and even numbers, there is a calculation.


For it, you are taking n times (50% of the time a number is even or odd).


.


If not sorted, the runtime will change, and it will break binary search, since the input needs to be sorted.


Code for Binary Search

public int bsearch(int[] arr, int el){
    int low=0;
    int high=arr.length;
    int mid=0;
    while(low < high){
        mid=(low+high) / 2 ;
        if(arr[mid] == el ){
            return mid; // position index
        }else if (arr[mid] < el ){
            low=mid+1;
//we checked middle already
        }else{
            high = mid-1;
//we check ed middle already
        }
    }
//if we came here
//it means we couldn’t find it
    return -1;
}

The possibility scales up binarily.


While in theory, iterative and recurisve binary search are the same speed, but in reality, iterative Binary Search is faster, since recurive needs function calls, which forms a program stack, which does take up space.