Time Complexity and Big O Notation

Time complexity describes how an algorithm’s work grows with input size. It abstracts away exact processor speed so you can reject approaches that scale badly before implementing them. Big O is an upper bound, not an exact stopwatch prediction or a synonym for “worst case”; state which case is being analyzed. Our program counts visits in a linear loop, a triangular nested loop and repeated halving.

Prerequisites: Loops and basic arithmetic.

Build the idea

1. 1. Count repeated work

   A loop visiting n elements performs n body iterations, giving Θ(n) work when each body is constant-time. Two consecutive n-step loops perform 2n operations, still Θ(n). A loop over n elements containing another full n-step loop performs n² body iterations. Constants matter in practice, but asymptotic analysis keeps the dominant growth term.

2. 2. Do not classify by indentation alone

   In a triangular loop, the inner count is 0+1+…+(n−1)=n(n−1)/2, which is still Θ(n²). An inner pointer that only advances across the entire array may instead produce linear total work; later two-pointer lessons demonstrate this. Always total actual iterations rather than assuming any two visible loops mean n².

3. 3. Recognize logarithmic shrinking

   Repeatedly replacing a positive integer x by floor(x/2) takes about log₂n steps to reach one. For n=8 the states are 8,4,2,1 and there are three divisions. Combining O(log n) work per element gives O(n log n). Exponential enumeration, such as 2ⁿ subsets, doubles its state count when n increases by one.

4. 4. Compare scales using constraints

   At n=100000, n² is 10^10 iterations while n log₂n is roughly 1.7 million units of comparison-scale work. That strongly favors sorting or a logarithmic structure over checking every pair, though actual time depends on operation costs, language, machine and limits. There is no universally reliable “one second equals exactly X operations” rule.

   Growth	Typical source	Scale at n=1024
   O(1)	one indexed access	1
   O(log n)	repeated halving	10
   O(n)	one scan	1024
   O(n log n)	comparison sorting	about 10240
   O(n²)	all ordered pairs	1048576
   O(2ⁿ)	subsets	astronomical

5. 5. Analyze the complete example

   The program deliberately executes all three loops. For n=8 it prints 8,28,3. Its TOTAL runtime is dominated by the quadratic pair counter, not the fastest loop. Counting logical iterations is not benchmarking: an optimizing compiler may simplify these arithmetic loops. Use operation reasoning for growth and real measurements only when comparing actual implementations under meaningful inputs.

This is a complete program. Compile with C++17 and enter the input described below.

// Key idea: 5. Analyze the complete example The program deliberately executes all three loops.
#include<iostream>
int main(){
    int n;
    std::cin>>n;
    long long linear=0,pairs=0;
    for(int i=0;i<n;++i){
        ++linear;
    }
    for(int i=0;i<n;++i){
        for(int j=0;j<i;++j){
            ++pairs;
        }
    }
    int halvings=0;
    for(int x=n;x>1;x/=2){
        ++halvings;
    }
    std::cout<<linear<<' '<<pairs<<' '<<halvings<<'\n';
}

Complexity analysis

For the written algorithm, Θ(n²) time overall and O(1) auxiliary space. Separately, the first loop is Θ(n), the triangular loop Θ(n²), and the halving loop Θ(log n) for n≥2. The program limits n to 2000 because it intentionally demonstrates quadratic enumeration.

Example input and output

Integer n in 1..2000. Print the linear visit count, number of pairs with 0≤j<i<n, and divisions by two needed until n becomes one.

Input

8

Output

8 28 3

There are 8 single visits, 8×7/2=28 index pairs and three halvings: 8→4→2→1.

Practical applications

Use complexity to choose among complete search, sorting, preprocessing and specialized algorithms. Compare the largest allowed n, not just sample size. Then inspect constants, memory and implementation risk before choosing a final approach.

Check your understanding

What is the asymptotic growth of 1+2+…+n?

Put it into practice

Write down the work for n=16 without running the code.