Algorithms and Problem Solving with Java
Understanding Algorithmic Complexity and Big-O
You are viewing a free preview lesson.
Lesson Overview
একটি program correct হওয়া জরুরি।
কিন্তু production software-এ শুধু correct হলেই সবসময় যথেষ্ট নয়।
Suppose two methods একই result produce করে:
Method A → 1 millisecond
Method B → 10 seconds
Small input-এ difference হয়তো বোঝা যাবে না।
কিন্তু input বড় হলে difference huge হয়ে যেতে পারে।
এই কারণে algorithms নিয়ে ভাবার সময় আমরা শুধু জিজ্ঞেস করি না:
Does it work?
আমরা আরও জিজ্ঞেস করি:
How much work does it do?
Input বড় হলে work কত দ্রুত বাড়ে?
How much memory does it need?
এই lesson-এ আমরা শিখব:
- What an algorithm is
- Input size
- Why performance matters
- Time complexity
- Space complexity
- Big-O notation
O(1)O(log n)O(n)O(n log n)O(n²)- Why constants are usually ignored
- Best, average, and worst-case intuition
- How loops relate to complexity
- Nested loops
- Sequential operations
- Common Java collection complexity
- Performance tradeoffs
- Why Big-O is useful in backend engineering
What Is an Algorithm?
An algorithm is a finite sequence of steps used to solve a problem।
Example problem:
Find whether an array contains 42.
One possible algorithm:
Start from first element
Compare it with 42
If equal → return true
Otherwise move to next element
Repeat until found or array ends
Java implementation:
static boolean contains(
int[] numbers,
int target
) {
for (
int number
: numbers
) {
if (
number == target
) {
return true;
}
}
return false;
}
This is an algorithm।
Algorithms Are Not Only Fancy Problems
When people hear:
Algorithms
they sometimes think only about interview puzzles।
But everyday backend code contains algorithms everywhere।
Examples:
Search a collection
Sort records
Remove duplicates
Find highest value
Group data
Validate input
Process a queue
Match identifiers
Merge results
Paginate records
Build indexes
Cache lookups
Even a simple loop is implementing an algorithm।
Correctness Comes First
Before discussing performance:
The algorithm must be correct.
A fast wrong answer is still wrong।
A useful priority is:
1. Correctness
2. Clear design
3. Appropriate performance
4. Optimization where justified
Do not sacrifice correctness just to claim lower Big-O complexity।
What Is Input Size?
Complexity describes how resource usage changes as input grows।
We often represent input size with:
n
Example:
int[] numbers
If:
numbers.length = 10
then:
n = 10
If:
numbers.length = 1_000_000
then:
n = 1,000,000
Why Input Size Matters
Consider:
static void printAll(
int[] numbers
) {
for (
int number
: numbers
) {
System.out.println(
number
);
}
}
If the array has:
10 elements
the loop runs roughly:
10 times
If it has:
1,000,000 elements
the loop runs roughly:
1,000,000 times
The amount of work grows with input size।
Time Complexity
Time complexity describes how the amount of computational work grows as input size grows।
It does not normally mean:
Exact milliseconds
Instead, we ask:
How does work scale relative to n?
Examples:
O(1)
O(log n)
O(n)
O(n log n)
O(n²)
Why Not Measure Milliseconds?
Suppose the same algorithm runs on:
Laptop A
Server B
Phone C
Exact execution time may differ because of:
CPU
Memory
JVM optimization
Operating system
Current system load
Input values
But the growth pattern of the algorithm remains more stable।
That is what complexity analysis tries to capture।
Big-O Notation
Big-O describes an upper-bound growth pattern commonly used to reason about algorithm scalability।
Examples:
O(1)
O(log n)
O(n)
O(n log n)
O(n²)
For this course, think of Big-O as:
How quickly the amount of work grows
as input grows.
We are not focusing on mathematical proofs।
We are building practical engineering intuition।
O(1) — Constant Time
Suppose:
static int first(
int[] numbers
) {
return numbers[0];
}
Whether the array contains:
10 elements
or:
10,000,000 elements
we access one position।
Conceptually:
One operation
This is:
O(1)
Constant Does Not Mean Instant
O(1) does not mean:
Zero time
or:
Exactly one CPU instruction
It means:
The work does not grow with n.
Example:
static int calculate(
int[] numbers
) {
int first =
numbers[0];
int last =
numbers[
numbers.length - 1
];
return first + last;
}
This may perform several operations।
Still:
O(1)
because the number of operations remains roughly constant regardless of array size।
More O(1) Examples
Array index lookup:
numbers[50]
Usually:
O(1)
Checking size:
list.size()
for common Java collections such as ArrayList:
O(1)
Hash-based lookup is often discussed as average:
O(1)
for structures like HashMap, although real behavior has important caveats we'll discuss later।
O(n) — Linear Time
Consider linear search:
static boolean contains(
int[] numbers,
int target
) {
for (
int number
: numbers
) {
if (
number == target
) {
return true;
}
}
return false;
}
Worst case:
Check every element
For n elements:
Approximately n checks
Complexity:
O(n)
Linear Growth
If input doubles:
n → 2n
the amount of work roughly doubles।
Example:
100 elements
→ about 100 checks
1,000 elements
→ about 1,000 checks
1,000,000 elements
→ about 1,000,000 checks
This is linear growth।
Common O(n) Operations
Examples include:
Print every element
Sum an array
Find maximum
Count matching values
Linear search
Copy every element
Sum Example
static int sum(
int[] numbers
) {
int total =
0;
for (
int number
: numbers
) {
total +=
number;
}
return total;
}
Every value must be visited।
Complexity:
O(n)
Maximum Example
static int max(
int[] numbers
) {
int max =
numbers[0];
for (
int i = 1;
i < numbers.length;
i++
) {
if (
numbers[i] > max
) {
max =
numbers[i];
}
}
return max;
}
Again:
O(n)
O(n²) — Quadratic Time
Consider:
for (
int i = 0;
i < numbers.length;
i++
) {
for (
int j = 0;
j < numbers.length;
j++
) {
System.out.println(
numbers[i]
+ ", "
+ numbers[j]
);
}
}
Outer loop runs:
n times
For every outer iteration, inner loop runs:
n times
Total work:
n × n
which is:
n²
Complexity:
O(n²)
Why Quadratic Growth Matters
Suppose:
n = 10
rough operations:
100
If:
n = 100
operations:
10,000
If:
n = 10,000
operations:
100,000,000
Input increased by:
1000×
but work increased dramatically।
Duplicate Detection Example
Earlier we implemented:
static boolean hasDuplicate(
int[] numbers
) {
for (
int i = 0;
i < numbers.length;
i++
) {
for (
int j = i + 1;
j < numbers.length;
j++
) {
if (
numbers[i]
== numbers[j]
) {
return true;
}
}
}
return false;
}
Worst-case complexity:
O(n²)
because many element pairs may be compared।
But the Inner Loop Gets Smaller
You may notice:
j = i + 1
so the inner loop does not always run exactly n times।
Actual comparisons are closer to:
n(n - 1) / 2
But Big-O simplifies the growth।
Dominant term:
n²
Therefore:
O(n²)
Why Big-O Ignores Constants
Suppose:
3n
operations।
Big-O:
O(n)
Suppose:
100n
operations।
Still:
O(n)
Why?
Because as n grows, both grow linearly।
Big-O focuses on growth class rather than exact constant factor।
Example
Algorithm A:
10n
Algorithm B:
n²
For small n, the first may even perform more operations।
Example:
n = 5
10n = 50
n² = 25
But:
n = 1000
10n = 10,000
n² = 1,000,000
As input grows, the growth rate dominates।
Ignore Lower-Order Terms
Suppose an algorithm performs:
n² + n + 50
Big-O is:
O(n²)
because for large n, the n² term dominates।
Example
For:
n = 1,000,000
compare:
n² = 1,000,000,000,000
n = 1,000,000
50 = 50
The lower-order terms become relatively insignificant।
Sequential Loops
Consider:
for (
int value
: numbers
) {
process(
value
);
}
for (
int value
: numbers
) {
print(
value
);
}
First loop:
O(n)
Second loop:
O(n)
Together:
O(n + n)
which simplifies to:
O(2n)
and then:
O(n)
Nested vs Sequential
This is important।
Sequential:
for (...) {
}
for (...) {
}
is usually:
O(n)
if both are linear।
Nested:
for (...) {
for (...) {
}
}
is usually:
O(n²)
when both loops depend on the same n।
Different Input Sizes
Suppose:
for (
String learner
: learners
) {
...
}
for (
String course
: courses
) {
...
}
If:
learners size = n
courses size = m
complexity is:
O(n + m)
Do not automatically call everything:
O(n)
when multiple independent input sizes matter।
Nested Different Inputs
Example:
for (
String learner
: learners
) {
for (
String course
: courses
) {
...
}
}
Complexity:
O(n × m)
where:
n = learner count
m = course count
O(log n) — Logarithmic Time
Logarithmic algorithms repeatedly reduce the remaining problem size by a large factor।
A classic example:
Binary Search
Suppose we search a sorted array of:
1,000,000 elements
Instead of checking one by one, binary search repeatedly eliminates roughly half of the remaining data।
Conceptually:
1,000,000
↓
500,000
↓
250,000
↓
125,000
↓
...
After around only 20 reductions, the search space becomes tiny।
Understanding log n Without Mathematics
You do not need logarithm formulas to build intuition।
Ask:
How many times can I divide n by 2
until roughly 1 remains?
Examples:
n = 8
8 → 4 → 2 → 1
about 3 steps
n = 16
16 → 8 → 4 → 2 → 1
about 4 steps
n = 1,024
about 10 steps
n = 1,048,576
about 20 steps
This is logarithmic growth।
Why O(log n) Is Powerful
Input can grow massively while the number of additional steps grows slowly।
Example:
1 thousand elements
→ around 10 reductions
1 million elements
→ around 20 reductions
1 billion elements
→ around 30 reductions
This is why binary search is so effective on sorted data।
Binary Search Preview
Conceptually:
static boolean binarySearch(
int[] sorted,
int target
) {
int left =
0;
int right =
sorted.length - 1;
while (
left <= right
) {
int middle =
left
+ (
right - left
) / 2;
if (
sorted[middle]
== target
) {
return true;
}
if (
sorted[middle]
< target
) {
left =
middle + 1;
} else {
right =
middle - 1;
}
}
return false;
}
We'll study this properly in the next lesson।
Worst-case complexity:
O(log n)
O(n log n)
A very important complexity class is:
O(n log n)
You will commonly see it with efficient comparison-based sorting algorithms।
Examples:
Merge Sort
Many Quick Sort scenarios
Standard efficient sorting approaches
Intuition for n log n
Imagine:
n elements
and the algorithm performs roughly:
log n levels of work
with roughly:
n total work per level
Then:
n × log n
gives:
O(n log n)
Example Growth
Approximate comparison:
n = 1,000
O(n)
≈ 1,000
O(n log₂ n)
≈ 10,000
O(n²)
≈ 1,000,000
For large input, n log n is much more scalable than n²।
Complexity Growth Comparison
A rough ordering from more scalable to less scalable:
O(1)
O(log n)
O(n)
O(n log n)
O(n²)
This is not a statement that every O(n) method is faster than every O(log n) method for every tiny input।
It is about growth as input becomes large।
Visual Intuition
Imagine increasing input:
n
O(1)
---------
work stays roughly flat।
O(log n)
slow growth
O(n)
proportional growth
O(n log n)
faster than linear
but much slower than quadratic
O(n²)
rapid growth
Best Case
Some algorithms may finish faster depending on input।
Linear search:
for (
int number
: numbers
) {
if (
number == target
) {
return true;
}
}
Suppose target is first:
[42, 7, 9, 100, ...]
Only one comparison।
Best case:
O(1)
Worst Case
Suppose target is:
not present
or at the final position।
Then every element may be checked।
Worst case:
O(n)
Average Case
Average case tries to describe typical expected work under assumptions about input distribution।
This can become mathematically involved।
For this foundation course, know the distinction:
Best case
Average case
Worst case
When people casually state Big-O for searching, they often focus on worst-case scalability unless otherwise specified।
Be Precise About Cases
For linear search:
Best: O(1)
Worst: O(n)
For hash lookup, you may hear:
Average: O(1)
Worst: can degrade beyond O(1)
For algorithms, always ask:
Which case are we describing?
Space Complexity
Time is not the only resource।
Space complexity describes how additional memory requirements grow with input size।
Example:
static int sum(
int[] numbers
) {
int total =
0;
for (
int number
: numbers
) {
total +=
number;
}
return total;
}
Additional variables:
total
number
do not grow with array length।
Extra space:
O(1)
Creating a Copy
static int[] copy(
int[] numbers
) {
return Arrays.copyOf(
numbers,
numbers.length
);
}
A new array of size:
n
is created।
Additional space:
O(n)
Time and Space Can Differ
Example:
static int[] doubled(
int[] numbers
) {
int[] result =
new int[
numbers.length
];
for (
int i = 0;
i < numbers.length;
i++
) {
result[i] =
numbers[i] * 2;
}
return result;
}
Time:
O(n)
Extra space:
O(n)
In-Place Transformation
static void doubleValues(
int[] numbers
) {
for (
int i = 0;
i < numbers.length;
i++
) {
numbers[i] *=
2;
}
}
Time:
O(n)
Additional space:
O(1)
because no second n-sized array is created।
Space-Time Tradeoff
Sometimes extra memory makes an algorithm faster।
Example duplicate detection。
Naive:
Compare every pair
Time:
O(n²)
Extra space:
O(1)
A HashSet approach:
static boolean hasDuplicate(
int[] numbers
) {
Set<Integer> seen =
new HashSet<>();
for (
int number
: numbers
) {
if (
!seen.add(
number
)
) {
return true;
}
}
return false;
}
Typical time:
O(n)
Average-case hash operations assumed।
Extra space:
O(n)
We traded more memory for faster expected execution।
This Is Real Engineering
Often there is no universally "best" algorithm।
You may choose between:
Less memory
More CPU
or:
More memory
Less CPU
depending on the system's constraints।
Recursion and Space Complexity
Remember recursion?
static int sumTo(
int number
) {
if (
number == 0
) {
return 0;
}
return number
+ sumTo(
number - 1
);
}
Time:
O(n)
But the recursive call stack may grow to:
O(n)
space।
Iterative Version
static int sumTo(
int number
) {
int total =
0;
for (
int i = 1;
i <= number;
i++
) {
total +=
i;
}
return total;
}
Time:
O(n)
Additional space:
O(1)
This is one practical difference between recursion and iteration।
Analyze Simple Loops
Example:
for (
int i = 0;
i < n;
i++
) {
doSomething();
}
Assume:
doSomething()
is constant time।
Then:
O(n)
Loop Increment by Two
for (
int i = 0;
i < n;
i += 2
) {
doSomething();
}
This runs roughly:
n / 2
times।
Big-O:
O(n)
Why not:
O(n / 2)
?
Constant factors are dropped։
Loop Running 100 Times
for (
int i = 0;
i < 100;
i++
) {
doSomething();
}
If 100 does not depend on n, complexity is:
O(1)
Even though it performs 100 iterations।
Loop Doubling the Index
Consider:
for (
int i = 1;
i < n;
i *= 2
) {
doSomething();
}
Values:
1
2
4
8
16
32
...
The input range is repeatedly doubled।
Number of iterations:
O(log n)
Loop Halving a Value
int value =
n;
while (
value > 1
) {
value /=
2;
}
Again:
O(log n)
because the remaining value halves every iteration।
Nested Linear Loops
for (
int i = 0;
i < n;
i++
) {
for (
int j = 0;
j < n;
j++
) {
doSomething();
}
}
Complexity:
O(n²)
Three Nested Loops
for (...) {
for (...) {
for (...) {
}
}
}
If each runs n times:
O(n³)
We will not focus heavily on cubic algorithms here, but the multiplication principle matters।
A Loop Does Not Automatically Mean O(n)
Consider:
for (
int i = 0;
i < 10;
i++
)
This is:
O(1)
because iterations are fixed।
And:
for (
int i = 1;
i < n;
i *= 2
)
is:
O(log n)
Therefore:
Look at how the loop variable changes
and what it depends on.
Method Calls Matter Too
Suppose:
for (
int value
: numbers
) {
expensiveOperation(
numbers
);
}
If:
expensiveOperation(numbers)
itself loops through the whole array:
O(n)
then outer loop:
n × n
makes total:
O(n²)
Do not analyze only visible loop syntax।
Analyze the work done by called methods too।
Hidden Complexity in Library Calls
Consider:
list.contains(
value
);
Its complexity depends on the collection implementation।
For:
ArrayList
contains() generally scans elements:
O(n)
For:
HashSet
contains() is typically average:
O(1)
The same-looking method call can have different complexity depending on data structure।
Common Java Collection Complexity
You do not need to memorize every implementation detail yet।
But these broad patterns are useful।
ArrayList
Common operations:
get(index) → O(1)
set(index, value) → O(1)
append → amortized O(1)
contains → O(n)
remove from middle → O(n)
remove first → O(n)
Why is get(index) fast?
Because ArrayList is backed by an array-like structure and can directly locate an index।
LinkedList
Broadly:
add/remove at known ends → O(1)
get(index) → O(n)
contains → O(n)
This is one reason collection choice should reflect how data will be accessed।
In modern Java, ArrayDeque is generally a stronger choice than LinkedList for straightforward Queue/Deque use cases।
HashSet
Typical:
add → average O(1)
contains → average O(1)
remove → average O(1)
But hashing has collision and worst-case considerations।
The important intuition:
Hashing is designed for fast lookup by value.
HashMap
Typical:
put(key, value) → average O(1)
get(key) → average O(1)
containsKey → average O(1)
remove → average O(1)
This is a major reason HashMap is so important in backend applications।
ArrayDeque
Operations at ends such as:
addFirst()
addLast()
pollFirst()
pollLast()
are generally efficient, typically amortized:
O(1)
This is why it works well for:
Queue
Deque
Stack
use cases।
Collection Choice Changes Algorithm Complexity
Suppose we have:
n learners
and for every learner we ask whether an email is in a collection।
If collection is:
List<String>
and contains() is:
O(n)
then repeated lookup inside another n loop can approach:
O(n²)
Using a HashSet
If lookup collection is:
Set<String> emails =
new HashSet<>();
and membership checks are typically average:
O(1)
then processing n learners may remain around:
O(n)
average expected time।
The data structure can completely change the algorithmic behavior।
Example: Duplicate Email Detection
Version 1:
static boolean hasDuplicate(
String[] emails
) {
for (
int i = 0;
i < emails.length;
i++
) {
for (
int j = i + 1;
j < emails.length;
j++
) {
if (
emails[i].equals(
emails[j]
)
) {
return true;
}
}
}
return false;
}
Worst case:
O(n²)
Hash-Based Version
static boolean hasDuplicate(
String[] emails
) {
Set<String> seen =
new HashSet<>();
for (
String email
: emails
) {
if (
!seen.add(
email
)
) {
return true;
}
}
return false;
}
Typical expected time:
O(n)
Extra memory:
O(n)
Complexity Is About Scale, Not Ego
Do not look at:
O(n²)
and automatically conclude:
Bad code.
For:
n = 10
a clear O(n²) solution may be perfectly acceptable।
If the maximum data size is tiny and fixed, additional complexity may not matter।
Example
Suppose business rule says:
A course can contain at most 20 prerequisite codes.
A simple pairwise comparison might be entirely reasonable।
But:
Compare every user against every other user
when there are:
20 million users
is a completely different situation।
Ask About Expected Input Size
Before optimizing, ask:
How large can n become?
How often is this operation executed?
Is it on a hot request path?
Is this a batch process?
Is the data already indexed?
Can we use more memory?
Do we need sorted output anyway?
This is engineering, not just complexity notation।
Big-O Does Not Tell You Everything
Two algorithms can both be:
O(n)
while one is considerably faster in real life।
Example:
Algorithm A → 2n simple operations
Algorithm B → 200n expensive operations
Both are:
O(n)
but constants matter in actual systems।
Big-O is a scalability model, not a complete performance benchmark।
CPU Cache and Memory Layout Matter
For example:
ArrayList
LinkedList
may have complexities that look similar for some operations, but actual runtime behavior can differ because of:
Memory locality
Object allocation
Pointer chasing
CPU caches
This foundation course does not go deep into hardware performance, but remember:
Big-O is one part of performance reasoning.
Database Complexity Is Different Too
Suppose backend code performs:
for (
User user
: users
) {
repository.findOrders(
user.id()
);
}
The Java loop itself may look:
O(n)
But if each iteration performs a database query, real cost could be huge।
This resembles the famous:
N+1 query problem
Algorithmic analysis should consider expensive external operations too।
Network Calls Matter
Consider:
for (
String id
: ids
) {
remoteService.fetch(
id
);
}
Even if technically:
O(n)
each operation may involve:
Network latency
Serialization
Remote processing
Retries
So Big-O alone cannot tell you whether the implementation is acceptable।
Big-O in Backend Engineering
Why should a backend engineer care?
Because systems commonly process:
Thousands of requests
Millions of users
Large event streams
Database records
Cache entries
Search results
Batch jobs
A design that seems fine with:
100 records
can collapse at:
10 million records
Example: Membership Check
Suppose every incoming request needs to check whether an API key has been revoked।
If revoked keys are stored in:
List<String>
each check may require scanning:
O(n)
If stored appropriately in:
HashSet<String>
lookup may be average:
O(1)
For a hot path, that difference can matter enormously।
Example: Pagination
Suppose a dataset contains millions of rows।
Page-based operations such as large SQL offsets can require increasingly more work depending on database and query design।
Cursor-based approaches may scale differently।
This course does not teach database pagination, but the same mindset applies:
How does work change as data grows?
Example: Logging Inside a Loop
Code:
for (
Event event
: events
) {
logger.info(
event.toString()
);
}
Algorithmically:
O(n)
But logging may involve:
String creation
Synchronization
Disk/network output
Again:
Complexity class ≠ complete performance story.
Premature Optimization
Do not transform readable code into complicated code just because:
"This looks more optimized."
without evidence or scale requirements।
A famous engineering principle is to avoid premature optimization।
Practical approach:
Choose reasonable algorithms and data structures first.
Measure when performance matters.
Optimize actual bottlenecks.
Complexity Helps Before Profiling
Profiling tells you:
Where time is actually being spent.
Complexity analysis helps you notice:
This algorithm fundamentally won't scale.
Both are valuable।
Practical Complexity Examples
Let's classify several examples।
Example 1
static int first(
int[] numbers
) {
return numbers[0];
}
Time:
O(1)
Extra space:
O(1)
Example 2
static void printAll(
int[] numbers
) {
for (
int number
: numbers
) {
System.out.println(
number
);
}
}
Iterations scale linearly।
Time:
O(n)
Extra space:
O(1)
excluding output-system internals।
Example 3
static int[] copy(
int[] numbers
) {
int[] result =
new int[
numbers.length
];
for (
int i = 0;
i < numbers.length;
i++
) {
result[i] =
numbers[i];
}
return result;
}
Time:
O(n)
Extra space:
O(n)
Example 4
static void printPairs(
int[] numbers
) {
for (
int first
: numbers
) {
for (
int second
: numbers
) {
System.out.println(
first
+ ", "
+ second
);
}
}
}
Time:
O(n²)
Example 5
static int getMiddle(
int[] numbers
) {
return numbers[
numbers.length / 2
];
}
Time:
O(1)
Example 6
static void process(
int n
) {
while (
n > 1
) {
n /=
2;
}
}
Time:
O(log n)
Example 7
static void process(
int[] first,
int[] second
) {
for (
int value
: first
) {
System.out.println(
value
);
}
for (
int value
: second
) {
System.out.println(
value
);
}
}
If:
first.length = n
second.length = m
time:
O(n + m)
Example 8
static void compareAll(
int[] first,
int[] second
) {
for (
int a
: first
) {
for (
int b
: second
) {
System.out.println(
a
+ ":"
+ b
);
}
}
}
Time:
O(n × m)
Complexity of Sorting
Efficient general comparison-based sorting is commonly around:
O(n log n)
for relevant average/worst guarantees depending on the algorithm।
Simple algorithms like:
Bubble Sort
Selection Sort
Insertion Sort
often have:
O(n²)
worst-case behavior।
We'll compare these later।
Why Learn Simple O(n²) Sorts?
Because they make core ideas visible:
Comparison
Swapping
Sorted vs unsorted regions
Algorithm invariants
Complexity
Once these are understood, algorithms like Merge Sort become easier to reason about।
Big-O Is Not About Counting Every Line
Consider:
int a =
1;
int b =
2;
int c =
3;
for (
int value
: numbers
) {
System.out.println(
value
);
}
You might count:
3 assignments + n loop operations
giving something like:
n + 3
Big-O:
O(n)
We care about growth, not exact line count।
Beware of Hidden Nested Work
Consider:
for (
String learner
: learners
) {
if (
enrolledLearners.contains(
learner
)
) {
...
}
}
If enrolledLearners is an ArrayList of roughly n elements:
outer loop → O(n)
contains → O(n)
Combined:
O(n²)
Change the Data Structure
If:
Set<String> enrolledLearners =
new HashSet<>();
then typical membership:
average O(1)
making total expected processing:
O(n)
This is why collection knowledge and algorithms belong together।
Common Mistake 1 — Every Loop Is O(n)
Wrong।
This:
for (
int i = 0;
i < 10;
i++
)
is:
O(1)
because loop count is fixed।
Common Mistake 2 — Two Loops Mean O(n²)
Not necessarily।
Sequential:
for (...) {
}
for (...) {
}
is often:
O(n)
Nested:
for (...) {
for (...) {
}
}
may be:
O(n²)
Common Mistake 3 — Ignoring Called Methods
This:
for (
Item item
: items
) {
findSomething(
items
);
}
can be quadratic if findSomething() itself scans all items।
Common Mistake 4 — Thinking O(1) Means One Instruction
It means constant growth relative to input size।
Common Mistake 5 — Thinking Big-O Predicts Exact Runtime
It does not।
Two O(n) implementations can have very different real-world speed।
Common Mistake 6 — Optimizing Tiny Data Unnecessarily
For a maximum fixed input size of 5 or 10 elements, an extremely simple algorithm may be preferable to a more complicated one even if its theoretical complexity is worse।
Common Mistake 7 — Ignoring Memory
Improving time complexity may require more space।
Example:
Nested duplicate search:
O(n²) time
O(1) extra space
HashSet duplicate search:
O(n) expected time
O(n) extra space
Common Mistake 8 — Calling Hashing Guaranteed O(1)
Better wording:
Average expected O(1)
for common HashMap/HashSet operations।
Worst-case behavior and implementation details are more nuanced।
Common Mistake 9 — Big-O as the Only Design Metric
Real software also cares about:
Correctness
Readability
Maintainability
Latency
Memory
Network calls
Database calls
Concurrency
Operational cost
Practice 1 — Classify Complexity
static int first(
int[] values
) {
return values[0];
}
Answer
O(1)
Practice 2
static int count(
int[] values
) {
int count =
0;
for (
int value
: values
) {
if (
value > 10
) {
count++;
}
}
return count;
}
Answer
O(n)
Practice 3
for (
int first
: values
) {
for (
int second
: values
) {
compare(
first,
second
);
}
}
Assume compare() is O(1)।
Answer
O(n²)
Practice 4
for (
int value
: values
) {
process(
value
);
}
for (
int value
: values
) {
print(
value
);
}
Assume both inner operations are constant time।
Answer
O(n)
because:
O(n + n)
→ O(2n)
→ O(n)
Practice 5
int value =
n;
while (
value > 1
) {
value /=
2;
}
Answer
O(log n)
Practice 6
int[] copy =
new int[
values.length
];
plus copying every element।
What is extra space?
Answer
O(n)
Practice 7 — Collection Choice
You have one million user IDs and need frequent membership checks।
Which is generally more suitable?
ArrayList
HashSet
Answer
Usually:
HashSet
because membership checks are typically average:
O(1)
instead of linear scanning।
Practice 8 — Find Hidden Complexity
List<String> enrolled =
new ArrayList<>();
for (
String learner
: learners
) {
if (
enrolled.contains(
learner
)
) {
...
}
}
Assume both collections grow proportionally to n।
Answer
ArrayList.contains() is linear।
So:
n outer iterations
×
n membership work
can lead to:
O(n²)
Practice 9 — Time vs Space
Algorithm A:
O(n²) time
O(1) extra space
Algorithm B:
O(n) expected time
O(n) extra space
Which is better?
Answer
There is not enough information।
It depends on:
Input size
Memory constraints
Execution frequency
Latency requirements
Implementation complexity
Practice 10 — Fixed Loop
for (
int i = 0;
i < 500;
i++
) {
process();
}
Relative to input size n, assuming 500 is always fixed:
Answer
O(1)
True or False
- Big-O normally describes exact milliseconds.
O(1)means work does not grow with input size.- Accessing an array by index is generally
O(1). - Traversing every array element is generally
O(n). - Two nested full
nloops are generallyO(n²). - Two sequential
O(n)loops becomeO(n²). - Binary search has logarithmic search complexity on sorted data.
- Efficient sorting commonly involves
O(n log n). - Big-O usually ignores constant factors.
O(n² + n)simplifies toO(n²).- Space complexity describes additional memory growth.
- Recursion may use extra call-stack space.
ArrayList.contains()is generally constant time.HashSet.contains()is typically averageO(1).- Big-O alone tells us everything about system performance.
Answers
1. False
2. True
3. True
4. True
5. True
6. False
7. True
8. True
9. True
10. True
11. True
12. True
13. False
14. True
15. False
Knowledge Check
Question 1
What is an algorithm?
Question 2
What does n normally represent in complexity analysis?
Question 3
What does O(1) mean?
Question 4
Give two examples of O(n) operations.
Question 5
Why are nested full loops often O(n²)?
Question 6
What kind of behavior usually produces O(log n)?
Question 7
Where do we commonly encounter O(n log n)?
Question 8
Why does Big-O ignore constant factors?
Question 9
What is the difference between time complexity and space complexity?
Question 10
Why can a HashSet improve duplicate detection compared with nested loops?
Question 11
Why should collection implementation be considered during complexity analysis?
Question 12
Why isn't a lower Big-O automatically the best solution for every program?
Knowledge Check Answers
Answer 1
An algorithm is a finite sequence of steps used to solve a problem or perform a computation।
Answer 2
n normally represents the size of the relevant input, such as the number of elements in an array or collection।
Answer 3
O(1) means the amount of work stays roughly constant as input size grows।
Answer 4
Examples:
Traversing all elements
Calculating a sum
Finding maximum
Linear search in the worst case
Answer 5
Because if the outer loop performs n iterations and the inner loop performs roughly n iterations for each outer iteration, total work is approximately:
n × n = n²
Answer 6
Repeatedly reducing the remaining problem by a constant factor, such as halving the search space in binary search।
Answer 7
Efficient general sorting algorithms commonly have O(n log n) behavior under relevant cases and guarantees।
Answer 8
Because Big-O focuses on how work grows for large input, and constant multipliers do not change the growth class।
Answer 9
Time complexity describes how computational work grows, while space complexity describes how additional memory usage grows।
Answer 10
Nested pair comparison may require O(n²) time, while storing previously seen values in a HashSet allows typical average constant-time membership checks, producing expected O(n) total time at the cost of O(n) extra space।
Answer 11
Because operations with the same method name can have very different performance depending on the underlying data structure।
For example:
ArrayList.contains()
→ O(n)
HashSet.contains()
→ average O(1)
Answer 12
Because actual engineering decisions also depend on:
Input size
Constants
Memory
Readability
Implementation complexity
Execution frequency
External I/O
Operational requirements
Practical Engineering Checklist
When you see a piece of code that processes data, ask:
What is n?
How many times is each element visited?
Are there nested scans?
Does a called method perform another scan?
Which collection implementation is used?
Could lookup be changed from linear to hash-based?
Is data already sorted?
Am I creating an n-sized copy?
Could recursion grow with n?
What is the expected real input size?
These questions matter more than memorizing complexity labels।
Complexity Cheat Sheet
A useful starting intuition:
O(1)
Constant work
O(log n)
Repeatedly reduce the problem
for example by half
O(n)
Process each item once
O(n log n)
Common efficient sorting territory
O(n²)
Compare many/all pairs
or perform nested linear scans
For scalability intuition:
O(1)
↓
O(log n)
↓
O(n)
↓
O(n log n)
↓
O(n²)
Generally, growth becomes progressively more expensive as input becomes large।
But engineering decisions always depend on context।
Lesson Summary
এই lesson-এ আমরা algorithmic complexity-এর foundation তৈরি করেছি।
We learned:
- An algorithm is a sequence of steps for solving a problem
- Complexity describes how resource usage grows with input size
ncommonly represents input size- Time complexity focuses on computational work
- Space complexity focuses on additional memory
- Big-O describes growth rather than exact runtime
O(1)represents constant growthO(log n)appears when the problem repeatedly shrinks by a factorO(n)represents linear growthO(n log n)is common in efficient sortingO(n²)commonly appears with nested linear work- Constants and lower-order terms are ignored when identifying growth class
- Sequential linear loops remain
O(n) - Nested linear loops may become
O(n²) - Different input sizes may produce
O(n + m)orO(n × m) - Best, average, and worst cases can differ
- Hash-based structures can trade extra memory for faster expected lookups
- Recursive algorithms may require additional stack space
- Collection choice can fundamentally change algorithm complexity
- Big-O is essential for scalability reasoning but does not replace profiling or real performance measurement
- Backend performance also depends on databases, networks, I/O, allocation, and other external costs
- The right algorithm depends on scale and requirements, not complexity notation alone
The most important mindset is:
Do not ask only:
"Does this work?"
Also ask:
"What happens when the data becomes
10 times, 1000 times,
or one million times larger?"
That question is the beginning of algorithmic thinking।
Next Lesson
পরবর্তী lesson:
Linear Search and Binary Search
আমরা শিখব:
- Searching as an algorithmic problem
- Linear Search implementation
- Best and worst cases
- Binary Search requirements
- Sorted input
left,right, andmiddle- Implementing Binary Search manually
- Tracing the algorithm
O(n)vsO(log n)Arrays.binarySearch()Collections.binarySearch()- When sorting before search does and does not make sense