NAME: SCOTT PATRICK ABANG
MATRIC: VUG/CSC/22/7279
COURSE: CSC 311 - Algorithm and Time Complexity
1. Nested For Loop:
cpp
Copy code
For(i=0; i<n; i++) {
For(j=0; j<i; j++) {
stmt;
}
}
● Outer loop runs from i=0 to n-1, i.e., n iterations.
● Inner loop runs from j=0 to i-1, i.e., i iterations for each value of i.
The total number of iterations is:
Sum of iterations=∑i=0n−1i=n(n−1)2≈O(n2)\={Sum of iterations} = \sum_{i=0}^{n-1}
i = \frac{n(n-1)}{2} \approx O(n^2)Sum of iterations=i=0∑n−1i=2n(n−1)≈O(n2)
● Time Complexity: O(n²)
2. Double Loop with Multiplicative Outer Loop:
cpp
Copy code
For(i=1; i<n; i*=2) {
For(j=0; j<i; j++) {
stmt;
}
}
● Outer loop: Starts at i=1 and doubles each time (i *= 2). The number of
iterations is approximately log2(n)\log_2(n)log2(n).
● Inner loop: Runs i times, but i varies as powers of 2: 1,2,4,8,…1, 2, 4, 8,
\ldots1,2,4,8,….
The total number of iterations is:
Sum of iterations=1+2+4+8+…+n≈O(n)\text{Sum of iterations} = 1 + 2 + 4 + 8 +
\ldots + n \approx O(n)Sum of iterations=1+2+4+8+…+n≈O(n)
● Time Complexity: O(n)
3. Nested Loops with Multiplicative and Divisive Steps:
cpp
Copy code
For(i=1; i<n; i*=2) {
For(j=1; j<i; j/=3) {
stmt;
}
}
● Outer loop: Same as before, log2(n)\log_2(n)log2(n) iterations.
● Inner loop: Starts at j=1 and divides j by 3 on each iteration. It terminates
quickly, running approximately log3(i)\log_3(i)log3(i) times.
The total iterations:
Outer loop iterations: log2(n),Inner loop: log3(i).\text{Outer loop iterations: }
\log_2(n), \quad \text{Inner loop: } \log_3(i).Outer loop iterations: log2(n),Inner
loop: log3(i).
The total work is:
∑i=1log2(n)log3(i)≈O(logn⋅loglogn)\sum_{i=1}^{\log_2(n)} \log_3(i) \approx O(\log
n \cdot \log \log n)i=1∑log2(n)log3(i)≈O(logn⋅loglogn)
● Time Complexity: O(log n × log log n)
4. Binary Search Algorithm:
● Binary Search divides the array in half at every step, reducing the search
space by half until the element is found or the search space is empty.
● The number of iterations is approximately log2(n)\log_2(n)log2(n).
● Time Complexity: O(log n)
5. Worst Case of Linear Search:
● Linear Search scans each element of the array until the value is found or the
end is reached.
● In the worst case, the algorithm examines all n elements.
● Time Complexity: O(n)
