Member Avatar for nabil1983

Trying to understand how to do this Q. Can some explain using O-notation, how would i analyse the efficiency of the two algorithms below. ?

Assuming that the critical operation is compute and size is the size of the array.

1) compute(a[1]) + compute(a[2]) + compute(a[3]) + compute(a)

2) for k = 1 to size for j = 1 to size compute(a[j])

I just need someone to xplain this briefly so that i can understand how i would analyze algorithms of such in the future.

Also what is meant by the terms 'Programming Time' and 'Execution Time' in relation to algorithms.?

Apreciate ne help

  • 2 Contributors
  • 2 Replies
  • 116 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by nabil1983

Dani AI

Generated

A short, practical way to do these analyses (for ):

  1. Pick the input-size variable (here size) and the critical operation (compute).
  2. Express an exact count of how many times compute runs as a function of size.
  3. Keep the highest-order term, drop constants and lower-order terms — that gives the Big‑O.

Two points about the two snippets in the first post (there is a little ambiguity in the literal text, so both interpretations are shown):

  • If the first line is a fixed, constant number of compute calls (for example exactly 3 or 4 calls regardless of size), the count does not grow with size and the complexity is O(1) (constant).
  • If the intention is a call for every array element (i.e., compute(a[1]) + compute(a[2]) + ... + compute(a[size])), then compute runs size times and the complexity is linear: T(size) = c*size so O(size).

For the nested loops (for k = 1 to size then for j = 1 to size do compute(a[j])): the inner loop does size calls for each of the size outer iterations, so total calls = size * size = size^2. If a single compute is O(1), the whole routine is O(size^2).

About "Programming Time" vs "Execution Time": programming time refers to human development effort (design, coding, testing). Execution time is how long the program runs on a machine. As pointed out, wall‑clock measurement is useful, but combine profiling with asymptotic analysis: run multiple inputs, vary size, and check that observed timings follow the predicted growth (linear, quadratic, etc.). Also watch for constant factors, I/O or library costs, and cases where compute itself may not be O(1) — incorporate its cost into the final expression.

Recommended Answers

All 2 Replies

Member Avatar for Ancient Dragon

Also what is meant by the terms 'Programming Time' and 'Execution Time' in relation to algorithms.?

how long time it takes for the algorithm to execute. For example, if testing a sort algorithm, how long does it take the alogithm to sort the data. That is normally measured by getting current system time before starting the algorithm, again after and subtacting the two.

clock_t t1 = clock(); // get start time
// do algorithm
clock_t t2 = clock();// get end time

clock_t delta_time = t2 - t1; // difference
Member Avatar for nabil1983

thanx bro.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.