Question

Need some help with finding the runtime of these java functions in the form of exact, tilde and big oh notation:

Example of how:

Func	Exact	Tilde	O()
Example 1	1	~1	O(1)
Example 2	2n+1	~2n	O(2n)

Here are the functions:

void funcA(int n) {

        step();

        for (int i = 0; i < n; i++) {

            funcA(n-1);

        }

    }

    void funcB(int n) {

        step();

        if (n > 0)

            funcB(n-1);

    }

    void funcC(int n) {

        step();

        if (n > 0) {

            funcC(n/2);

        }

    }

  

void funcD(int n) {

        if (n > 0) {

            funcD(n/2);

        }

        for (int i = 0; i < n; i++) {

            step();

        }

        if (n > 0) {

            funcD(n/2);

        }

    }

void funcE(int n) {

        Random random = new Random();

        int target = random.nextInt(n);

        int lo = 0;

        int hi = n;

        while (hi - lo > 1) {

            step();

            int mid = (lo + hi) / 2;

            if (mid > target) {

                hi = mid;

            }

            else {

                lo = mid;

            }

        }

    }

   

void funcF(int n) {

        step();

        if (n > 0) {

            funcF(n-1);

            funcF(n-1);

            funcF(n-1);

        }

    }

   

void funcG(int n) {

        for (int i = 0; i < n; i++) {

            step();

            for (int j = 1; j <= n; j *= 3) {

                step();

            }

        }

    }

   

void funcH(int n) {

        step();

        for (int i = 1; i <= n; i *= 2) {

            step();

            step();

        }

        for (int i = 0; i <n; i++) {

            step();

        }

    }

   

void funcI(int n) {

        int i = n * n * n;

        while (i > 0) {

            step();

            for (int j = 0; j * j < n; j++) {

                step();

                i--;

            }

        }

Answer 1

void funcA(int n) {

        step();

        for (int i = 0; i < n; i++) {

            funcA(n-1);

        }

    }

Exact: n*(n-1)

Tilde: ~n²

O(): O(n²)

    void funcB(int n) {

        step();

        if (n > 0)

            funcB(n-1);

    }

Exact: n-1

Tilde: ~n

O(): O(n)

    void funcC(int n) {

        step();

        if (n > 0) {

            funcC(n/2);

        }

    }

Exact: log₂n

Tilde: ~log₂n

O(): O(log₂n)

  

void funcD(int n) {

        if (n > 0) {

            funcD(n/2);

        }

        for (int i = 0; i < n; i++) {

            step();

        }

        if (n > 0) {

            funcD(n/2);

        }

    }

The recurrence relation is given as: T(n) = 2T(n/2) + O(n)

Exact: n*log₂n

Tilde: ~n*log₂n

O(): O(n*log₂n)

NOTE: As per HOMEWORKLIB POLICY I am allowed to answer 4 questions (including sub-parts) on a single post. Kindly post the remaining questions separately and I will try to answer them. Sorry for the inconvenience caused.