# Your DSA starting point
FindTutor • Original university revision notes

## What are we measuring?
An algorithm is a sequence of steps for solving a problem. A data structure organises data to support operations. Time complexity describes how work grows as input size n grows; it does not give an exact time in seconds.

Big-O gives an asymptotic upper bound. In introductory comparisons, specify whether you are discussing best, average or worst case.

| Operation / algorithm | Typical time bound | Important condition |
|---|---|---|
| Array access by index | O(1) | Direct indexing |
| Linear search | O(n) worst case | Works on unsorted input |
| Binary search | O(log n) worst case | Sorted, random-access sequence |
| Merge sort | O(n log n) | Standard implementation |
| Two complete nested n-item loops | O(n²) | Constant work per inner step |

## Linear search
Check each item until you find the target or reach the end. For [8, 2, 11, 5], finding 11 takes 3 equality checks. Finding 9 takes 4 checks and fails.

## Binary search
Given [2, 5, 8, 11, 14, 17, 20], search for 17:
1. Middle index 3 holds 11. Search the right half.
2. Middle index 5 holds 17. Found after two checks.

```python
def binary_search(items, target):
    low, high = 0, len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        if items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1
```
The input must already be sorted in ascending order. This implementation returns one matching index if duplicates exist; it does not promise the first match.

## Stack versus queue
A stack is last-in, first-out: push adds at the top, pop removes from the top. Example: undo history.
A queue is first-in, first-out: enqueue adds at the rear, dequeue removes from the front. Example: waiting print jobs.
The operation cost depends on the implementation. Removing the first item from a Python list shifts the remaining elements; a suitable deque avoids this.

## Practice
1. What is the worst-case complexity of scanning n items twice, one scan after another?
2. What changes if one n-item loop is inside another?
3. Why can't the binary-search implementation above reliably search an unsorted list?
4. Push A, push B, pop, push C, pop. What values are removed?
5. In binary search, why use mid + 1 instead of mid when moving low?

## Answers
1. O(n): 2n grows linearly, and constant factors are omitted.
2. O(n²), assuming constant work per iteration and both loops run n times.
3. Comparing with the middle value no longer tells us which half can be discarded.
4. B, then C. A remains.
5. The middle element has already been checked. Excluding it guarantees progress and prevents a stuck search interval.

Study with your own course outline; implementation details and required proofs vary by university.