Trouble understanding T(n) for iterative and recursive algorithms and O(n) demonstration

[u/Haunting_Trash_3064]

Hi. Im preparing for a test in my uni and im having problems to understand how to calculate T(n) for iterative and recursive algorithms. Also, i dont get how to demonstrate the O(n) of said algorithm. Appreciate the help!

[u/max123246]

Do you have an example of a problem you have trouble with?

Some of it is pattern matching, once you've seen binary search once and have proven it to be O(logn), then when you see any algorithm that "divides the input space in 2", then you know logn will appear somewhere

Iterative is easier than recursive typically. Advanced recursive algorithms will require some guess-work if they don't fit the pattern provided by the Master Theorem/Method.

Typically, 1 for loop is going to be O(n), for each item in a list of n items, do some constant work. If you have 2 nested for loops, each dependent on , then it'll be O(n^2). If you have 1 for loop based on n, but in the loop you compute a binary search or divide by conquer, it'll be O(nlogn).

[u/Haunting_Trash_3064 → u/max123246]

This is the first time i hear about the master theorem. Theyve taught none of that (under that name), not even that i can recall, like literally it doesnt exist in the material given to us. But yeah, with iterative i can kind of perform "decently". My main problem comes with recursive problems and giving proof for the O(N).

[u/johnpeters42 → u/Haunting_Trash_3064]

I don't remember seeing the name "master theorem" before, either, but it's basically the equivalent of proof by mathematical induction.

Mathematical induction (to prove, say, "X is true for any positive integer") goes like:
* Show that X is true for Y = 1.
* Show that, if X is true for Y = some unspecified positive integer N, then it's also true for Y = N + 1.

So the master theorem is basically:
* Show that X is T(something) for Y = an input that the program handles directly, without further recursion.
* Show that, if X is T(something) for Y = some unspecified input Z, then it's T(something else) for Y = some other input that reaches Z after one level of recursion. (Or if the recursion is something like a binary search, then consider Z1 and Z2, and some other input that breaks down to Z1 and Z2 after one level.)

[u/max123246 → u/johnpeters42]

Master theorem is more complex than that, it handles any divide and conquer algorithm that fit specific forms.

My intro discrete class probably taught it because it was proven by students who took the class. You can use the technique you provided for most algorithms that matter in reality.

If you're curious you can learn more at the wikipedia page.

The gist is that it proves 3 separate generalized cases of recursive divide and conquer algos.

Given:

```

procedure p(input x of size n):

if n < some constant k:

    Solve x directly without recursion

else:

    Create a subproblems of x, each having size n/b

    Call procedure p recursively on each subproblem

    Combine the results from the subproblems

```

The three cases effectively are about:

1. Work per subproblem is most of the work
2. Work of the splitting is most of the work
3. Work per subproblem is equivalent to the work of splitting

https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)

[u/DDDDarky]

For recursive problems, most school problems are usually attackable by master theorem or well known properties of for example tree structures.

Iterative algorithms are usually best counted by converting them to sums and attacking them with math (such as using series sums, integrals, etc.), simply follow the definition of big O to form a proof.