Algorithm Complexity - Exercises

Question

I study the exam in an introductory course in computer science, and I have a problem with the problem of complexity, both in "ordinary" algorithms and in recursive algorithms (usually we get these questions written as C code).
I was wondering if there are online examples somewhere on the Internet and / or a book that covers the topic at a basic level (not too simple).
the level of questions is at least as follows:

fetch alt text http://img42.imageshack.us/img42/4456/ex1j.jpg

Answer 1

I found a very good explanation in Introduction to Algorithms .... but you need knowledge of mathematics to understand this.

Lecture (video) for the course "Introduction to Algorithms" from the Massachusetts Institute of Technology regarding Asymptotic Notation here .

Answer 2

An Introduction to Cormen, Leiserson, and Rivest Algorithms is the best general introduction to algorithms that I know of.

The design and analysis of computer algorithms by Aho, Hopcroft and Ullman is also good. But it’s more difficult to digest the introductory text than an introduction to the algorithms ...

And I love programming the pearls of John Bentley. Everyone should read it.

Answer 3

I would also recommend following these video lectures from the Massachusetts Institute of Technology, available at: http://academicearth.org/courses/introduction-to-algorithms .

Good luck

Answer 4

My first advice to you would be that you don’t move on to new topics until you get Complexity. As for the text to be consulted, Introduction to the Cormen algorithm is a good option. See Basically, three ways to express the complexity of Big-oh, omega, and theta notations. The complexity calculation for iterative algorithms is quite simple. Go through any book and give examples. For a recursive algorithm, read the Wizard theorem . Using this theorem, you can easily calculate complexity for most recursive questions. Find the wizards theorem online and you will find some good lessons. You can start here http://en.wikipedia.org/wiki/Master_theorem .

Answer 5

The formal way to solve your exercise:

To check, run the following C program (MinGW2.95 compiler):

#include <stdio.h> #include <math.h> int main() { int sumIN = 0, sumOUT = 0; double i, n = 500, j; double d; for (i = 1; i <= n; i ++) { d = 1/(double)i; j = i; while (j > 0 && d > 0) { j -= d; sumIN ++; } sumOUT ++; } printf("\nsumIN = %d, sumOUT = %d", sumIN, sumOUT); printf("\n"); return 0; }