time complexity linear time calculation

Big O Notation O(n) expression:
1.find the fastest growing term
2.take out the coefficent

Backlog

Algorithms definition : a set of small steps (tasks) to solve a problem
human ex :
- go to kitchen
- pick up the egg and oil
- heat up the pan
- make an omlete
computer ex:
- wrote an f(n) where n is the array
- create pi_array a variable which should store pi number of num index in n
- write a for loop that loop trough the value , index on n in array
- with every iteration calculate the pi and add it to pi_array
- after ending the iteration return the pi_array
— Time Complexity : O(n) >
O(1) : pi_array + n x O(1) : for loop + O(1) = O(n) => Time grows as input gets larger

some things to note :
- in time complexity calculation we doesn't calculate the memory allocation of something like f(n)
- with every loop in the function the (n) get's powerd by 1 something like : O(n2).
- in time complexity we measure the worst case scenario like if a constant time was 0.0100 we wrote it O(1) because it's never 1 is the worsest scenario.

Mathematically, if f(n) describes the running time of an algorithm; f(n) is O(g(n)) if there exist positive constant C and n0 such that,

Just like O notation provide an asymptotic upper bound, Ω notation provides asymptotic lower bound.

In computer science, and more specifically in computability theory and computational complexity theory, a model of computation is a model which describes how an output of a mathematical function is computed given an input. A model describes how units of computations, memories, and communications are organized.[1] The computational complexity of an algorithm can be measured given a model of computation. Using a model allows studying the performance of algorithms independently of the variations that are specific to particular implementations and specific technology.


در نظریه رایانش پذیری و نظریه پیچیدگی محاسباتی، مدل محاسبه مدلی است که نحوه محاسبه خروجی یک تابع ریاضی را با توجه به ورودی توصیف می‌کند. به بیانی دیگر مدل محاسبه تعریف مجموعه‌ای از عملیات‌های قابل قبول مورد استفاده در محاسبات و نسبت هزینه‌هایشان است. برای اندازه‌گیری پیچیدگی یک الگوریتم در زمان اجرا یا حافظهٔ مصرف شده، با فرض مدل خاصی از محاسبات استفاده می‌شود، در تجزیه و تحلیل منابع محاسباتی مورد نیاز بحث کردن در مورد محدودیت‌های الگوریتم یا رایانهها ممکن است. یک مدل نحوه سازماندهی واحدهای محاسبات، حافظه‌ها و ارتباطات را توصیف می‌کند.[۱]

```c
insertion_sort(item s[], int n)
{
int i,j; /* counters */
for (i=1; i<n; i++) {
j=i;
while ((j>0) && (s[j] < s[j-1])) {
swap(&s[j],&s[j-1]);
j = j-1;
}
}
}
```
An animation of the logical flow of this algorithm on a particular instance (the
letters in the word “INSERTIONSORT”) is given in Figure 1.1
Note the generality of this algorithm. It works just as well on names as it does
on numbers, given the appropriate comparison operation (<) to test which of the
two keys should appear first in sorted order. It can be readily verified that this
algorithm correctly orders every possible input instance according to our definition
of the sorting problem.

There are three desirable properties for a good algorithm. We seek algorithms
that are correct and efficient, while being easy to implement. These goals may not
be simultaneously achievable. In industrial settings, any program that seems to
give good enough answers without slowing the application down is often acceptable,
regardless of whether a better algorithm exists. The issue of finding the best possible
answer or achieving maximum efficiency usually arises in industry only after serious
performance or legal troubles.

algorithm correctly solves a given problem. Correct algorithms usually come with
a proof of correctness, which is an explanation of why we know that the algorithm
must take every instance of the problem to the desired result

The following pseudocode presents a simplified version of the tabu search algorithm as described above. This implementation has a rudimentary short-term memory, but contains no intermediate or long-term memory structures. The term "fitness" refers to an evaluation of the candidate solution, as embodied in an objective function for mathematical optimization.

pseudocode of tabu search :

sBest ← s0
bestCandidate ← s0
tabuList ← []
tabuList.push(s0)
while (not stoppingCondition())
    sNeighborhood ← getNeighbors(bestCandidate)
    bestCandidateFitness ← -∞
    for (sCandidate in sNeighborhood)
        if ( (not tabuList.contains(sCandidate)) 
            and (fitness(sCandidate) > bestCandidateFitness) )
            bestCandidate ← sCandidate
            bestCandidateFitness ← fitness(bestCandidate)
        end
    end
    if (bestCandidateFitness is -∞)
        break;
    end
    if (bestCandidateFitness > fitness(sBest))
        sBest ← bestCandidate
    end
    tabuList.push(bestCandidate)
    if (tabuList.size > maxTabuSize)
        tabuList.removeFirst()
    end
end
return sBest