Introduction to Algorithm Complexity Analysis
The frequency count method assigns one unit of time per statement and counts how many times each statement executes to determine the total time taken by an algorithm. For a foundational understanding of why this matters, see our guide on Understanding Time and Space Complexity: A Comprehensive Guide to Big O Notation.
Example 1: Sum of Array Elements
Algorithm: Finding sum of all elements in an array of size n
Time Complexity Calculation
- Initial assignment: 1 unit (executes once)
- Loop initialization: 1 unit
- Loop condition check: n + 1 times
- Loop body statements: n times each
- Final statement: 1 unit
Time function: f(n) = 2n + 3
- Highest degree term is n
- Complexity: Order of n (O(n))
Space Complexity Calculation
- Array (n words) + loop variable (1 word) + sum variable (1 word) + n variable (1 word)
- Total: n + 3
- Complexity: Order of n (O(n))
Example 2: Sum of Two Matrices
Algorithm: Adding two square matrices of dimension n × n
Time Complexity Calculation
With three nested statements:
- Outer loop: n + 1 times
- Inner loop body: n times each, executed n times from outer loop = n² times
- Each inner statement: n² times
Time function: f(n) = 2n² + n
- Highest degree term is n²
- Complexity: Order of n² (O(n²))
Space Complexity
- Three matrices (A, B, C): 3n² words
- Loop variables (i, j): 2 words
- n variable: 1 word
- Total: 3n² + 3
- Complexity: Order of n² (O(n²))
Example 3: Multiplication of Two Matrices
Algorithm: Multiplying two square matrices of dimension n × n
Time Complexity Calculation
Three nested loops create the highest complexity:
- Outer loops: n + 1 each
- Statements inside three loops: n³ times each
- Statements inside two loops: n² times each
Time function: f(n) = n³ + 3n² + 2n + 1
- Highest degree term is n³
- Complexity: Order of n³ (O(n³))
Space Complexity
- Three matrices: 3n² words
- Loop variables (i, j, k): 3 words
- n variable: 1 word
- Total: 3n² + 4
- Complexity: Order of n² (O(n²))
Key Takeaways
- Frequency count method assigns execution counts per statement
- Complexity is determined by the highest degree term in the time/space function. For a more detailed breakdown of these concepts, check out Time & Space Complexity Basics: Big O Notation Explained for DSA.
- Different algorithms show increasing complexity:
- Array sum: O(n)
- Matrix addition: O(n²)
- Matrix multiplication: O(n³)
- Time and space complexity can differ (e.g., matrix multiplication: time O(n³), space O(n²))
knowledge is frequency count met her will did some algorithms and find out how this method is useful for five to
ten complexity of algorithms this algorithm is for finding sum of all the elements in an ie here is an array
assume that there's an ally of so many means I'm a piggelin array of size five with some elements in it so what is n +
5 so it is this array and NS 5 what this algorithm is to me it is finding is a form of all the elements in an array let
us analyze the time taken by the cell column so how do we do that by using frequency count method so the time taken
by an algorithm can be known by assigning one unit of time for each statement and if any statement is
repeating for some number of times the frequency of statement the frequency of execution of that statement will
calculate and we find that time taken by that Alberto so here we have some statement this is a statement which is
repeating for some number of times so we will find out its frequency and that will give us the time taken by the cell
kata so let us see so this is a simple statement so this takes one unit of time and as the C language code follow by
habit on this a C language for in this one we know of the still execute for one time and this will repeat for any time
but this condition will be checked for n plus 1 time how when n is 5 the first time
I go zero is less than and when I is the one one is less than n I used to tool is less than n is a 3/3 those who lived an
N for those who less than fighters not less than n so it will stop so I was initially already zero so how many times
I has changed fight ends then how many times condition is checked one two three four five six times five plus one four
times it was true and fair time it was false when it became five it was false so it has stopped so this is executing
400 us one times so you say that if you sum up this this is 2 n plus 2 but we write n plus 1 so it means we are
bothered about this phenomena right we have whatever only this one we don't want to write about those things usually
it is written n plus 1 only but if you observe it carefully it is true L plus true but we don't want to write the time
taken by these two right as I said we'll be doing it briefly then whatever the statement is there inside this room I
ask this is repeating for n times this is statement alone so we paid for at times so this is n times so now we can
understand that whatever is written in the loop like this type of loop the statement legible for n times and the
loop itself if you take it will execute for n plus 1 times then the last statement it will make you for one time
then what's the time function f of n is 2 n plus 1 2 3 that's it this is the time function now
what is the degree of that polynomial it is a degree one it is just n so we say order off and I am calling it as order
of I am NOT saying big or theta we will learn it in some other video now for now I will say order of n this complexity
see what are the variables used here it is used and s and the size of is and words and all these are just one one
word so total is how much n plus 3 so that space complexity is s of NS n plus 3
now this polynomial is also degree n so we say Otto space complexity we got it as order of N and the time complexity is
also order now Nextel governments for finding the sum of two matrices a and B are square matrices of dimension n cross
n cross n for example it is 3 cross 3 then these mattresses or two-dimensional arrays of size 3 by 3 dimensions are 3
where we assume that so n by n there and wagon now here I have an algorithm for finding the sum of two matrices let us
find out the time complexity for this one for them already you know this will take n plus 1 time now whatever is there
inside this loop will is u4 n times this is and this is all and two legs are two statements are they
each is taking and then what is this again the Zulu so focus also and blessed one then the game whatever is there
inside this one will execute for ten times that's it nor is the time taken by this one F of n
is and square and square 2 m squared plus and this is the time function for this what is the degree highest degree 2
so we don't write degree V night and square or rough and square so we are writing the degree we are not saying
that it is equal to this one we are saying that degree of this polynomial is n square that's all this is the time
complexity little state space complexity what are the variables that is having a we see the B and C I and I J what are
ABC they are matrices two dimensional arrays and cross n and square and square and square
what are an i J they are scalar variables simple variables one word one word one word
so space function is 3 and square plus 3 then what is the degree and square so this
also and square space complexity is also N squared so the time and the space complexity of this algorithm is N
squared how to find the time complexity I have shown it here how to find the space complexity I have shown it here
so for few algorithms I'm going to be showing for any other algorithm you can find out this one by following this
approach next algorithm is multiplication of two matrices you can see that there are three loops nested
one inside another one inside another let us find out the time on this side I would write this would be little far
away so this side is right so you can see them this is n plus 1 whatever is there inside will execute
for and dimes every statement and times then again this a loop so this is n plus 1 whatever is there inside it will
execute for n times so into n into n 2 then again this loop so this is n plus 1 times whatever is there inside will
execute for n times again so as the statement is inside all 3 loops so this is going to execute 4nq times this is
inside just these two lose these two so this is executing for n square and these are mu step so that's n plus 1 and
this is n square and thank you if you finally write down the time function f of n will be equals to C thank you and
one more and q2 and u plus this is the N squared and this is M square and this one wooden square so three n square plus
this is one n + 2 n so 2 n plus 1 that's it now you've got the degree of the polynomial as Q so the time function is
order off and you order of n cube policy space for this one space complexity for this one video sorry a B and C is a b
and c and i j k and i'm g + k this is a matrix so n square and square and square and all these are 1 1 1 so this is
spaces 3 and squared plus 4 so this is order of n square time is order of n cube spaces or rough n square you can
have a look at this working so that's it so I have shown you three different algorithms taking different
amount of time one was water of N and N squared and n cube next video you can watch the different type of algorithms
and also the method how to analyze them
The frequency count method is a technique that assigns one unit of time to each statement in an algorithm and counts how many times each statement executes. This total execution count is used to determine the algorithm's time complexity as a function of input size.
For an array sum of size n, each statement's execution count is tallied: initial assignment (1), loop initialization (1), condition check (n+1), loop body statements (n each), and final statement (1). This yields a time function of f(n) = 2n + 3, which simplifies to O(n) linear complexity.
Matrix addition uses two nested loops iterating n times each, resulting in n² operations total. Matrix multiplication requires three nested loops (i, j, k) each running n times, producing n³ operations. The highest-degree term in the time function determines this difference: 2n² vs. n³.
Both algorithms require storing three matrices (A, B, C) of dimension n×n, contributing 3n² words. However, matrix multiplication uses three loop variables (i, j, k) while addition uses two (i, j). Both have total space complexity O(n²) since the n² term dominates.
The highest degree term in a time or space function (e.g., n³ in n³ + 3n² + 2n + 1) dominates the function's growth as input size increases. Lower-order terms and constants become negligible for large inputs, so complexity is expressed using just this term (e.g., O(n³)).
Yes, as shown with matrix multiplication: time complexity is O(n³) due to three nested loops, while space complexity is O(n²) because only matrices and loop variables are stored. This illustrates that efficient time usage may require more memory, and vice versa.
By assigning execution counts to each statement, the method produces a precise time function that reveals how an algorithm scales. Comparing these functions (e.g., O(n) vs. O(n²)) allows developers to choose the most efficient algorithm for large inputs.
Keep this summary
Save it to LunaNotes and it becomes a real note in your library — editable, searchable, and ready to turn into flashcards or a diagram. Free to start.
Save to LunaNotesOr summarise for another video.
32K+ people have turned 65K+ videos into notes
“Very useful tool. I'm using it for the last couple weeks and I'm loving it so far. Makes learning on YouTube a great experience.”
Bhai Chrome Web Store reviewThis summary and transcript were automatically generated using AI with the Free YouTube transcript summary tool by LunaNotes.
Related summaries
Understanding Time and Space Complexity: A Comprehensive Guide to Big O Notation
Explore the concepts of time complexity, space complexity, and Big O notation with practical examples.
How to Write and Analyze Algorithms: Time and Space Criteria
This tutorial explains how to write algorithms using flexible syntax, emphasizing clarity for human understanding over strict programming rules. It also covers the key criteria for analyzing algorithms—time efficiency and space consumption—with a basic example demonstrating constant time and space complexity.
Time Complexity Analysis of Loop Variations in Code
Learn to analyze time complexity for different loop structures, including multiplying counters (log n), incrementing counters (n), and nested loops (n log n). This guide covers key formulas and examples to master algorithmic efficiency.
Time & Space Complexity Basics: Big O Notation Explained for DSA
This video introduces time complexity and space complexity concepts for coding interviews. The instructor explains why time taken is not time complexity, defines Big O notation, and covers the three key rules for computing complexity: worst-case scenario, avoiding constants, and ignoring lower-order terms. It also covers space complexity, auxiliary vs input space, and the crucial rule of not modifying input data.
Asymptotic Analysis Part 3: Growth Rates & Time Complexity
Learn why we use asymptotic complexity instead of exact running times in algorithm analysis. This tutorial explains how time complexity depends on input size and why higher-order terms dominate for large inputs, using clear examples with array shifts and growth rate calculations.
Most viewed summaries
A Comprehensive Guide to Using Stable Diffusion Forge UI
Explore the Stable Diffusion Forge UI, customizable settings, models, and more to enhance your image generation experience.
Kolonyalismo at Imperyalismo: Ang Kasaysayan ng Pagsakop sa Pilipinas
Tuklasin ang kasaysayan ng kolonyalismo at imperyalismo sa Pilipinas sa pamamagitan ni Ferdinand Magellan.
Mastering Inpainting with Stable Diffusion: Fix Mistakes and Enhance Your Images
Learn to fix mistakes and enhance images with Stable Diffusion's inpainting features effectively.
Pamamaraan at Patakarang Kolonyal ng mga Espanyol sa Pilipinas
Tuklasin ang mga pamamaraan at patakaran ng mga Espanyol sa Pilipinas, at ang epekto nito sa mga Pilipino.
How to Install and Configure Forge: A New Stable Diffusion Web UI
Learn to install and configure the new Forge web UI for Stable Diffusion, with tips on models and settings.
Found this summary useful?
Take it with you. One click puts it in your own LunaNotes library.
Save to LunaNotes