Time Complexity بسم هللا الرحمن الرحيم
• Our target is to develop the relationship between the Input and the Operations
needed to be done to display the Output (Input vs Operations)
• Case status: based on the Time the Operations are done in it
o Best case the best state the input in (so the smallest time)
o Average case the Average state the input in (the average time)
o Worst case the worst case the input in (our target, the longest time)
• Using worst case Filters the best solution to the problem
• Case Notations:
o Omega Notation: in most cases smaller than reality
o Theta Notation: describes the exact asymptotic growth rate
o O Notation: Represents the upper bound of an algorithm's growth.
(the easiest)
• The real and definite Relationship between Input and Operations , got by generating
many test cases and calculate the definite number of operations and write it in a
graph, because this operation is not practical, We use approximate functions that
express the largest factor of time increase
• We especially notice the family of the relation (Constant(1), Linear(n),
quadratic(n^2), ...)
• We drop lower terms and focus on the significant (we take the worst)
o ()المليون و األلف و الميه جمب المليار ملهمش الزمه
• Time Complexity of Consecutive( )المتتاليةblocks is the addition,
and of nested blocks is the multiplication of them
• Nested repetitive blocks are multiplied
• If the code contains different branches(Like in switch case) pick the worst branch
in the terms of time complexity
• Constant time optimization: the code still has the same notation but takes a little bit
smaller time, which would be better
• O notations: tell you the range of time this code needs
seconds – minuets – hours -…
• O(1) with the increase of input the operations stills the same
• Harmonic series ??????????
• n represents the input parameter, Time rely
on, and can be any other character
•
• If the loop relies on n and s of steps, time
complexity would be O(n/s)
1|Page
Time Complexity بسم هللا الرحمن الرحيم
• Log number of operations the number take dividing by the base
()أقسم الرقم على البيز كام مره لحد ما الناتج يطلع بواحد
o Log2(32): 32 > 16 > 8 > 4 > 2 > 1 = 5 operations
o It is the contrast of the power
• Logs growth rate is so slow Log2(1019) = 64 (1019 is the max for log), so it is a great
time complexity
• The recursive methods time complexity = number of states * Time needed for each
state
• To calculate time Complexity for hard codes Trace the bias variables, how and
when it changes ?
• O(n!) is the worst time complexity you can make ever Recursive Tree
o Can be used if n < 12
• Each circle in the recursive tree represents a state
and each state calls two states
• Its Time Complexity = O(2^n) exponential func
• It is a high increasing time Complexity => for a 10
as input, Operations will be 1024
• n + (n - 1) + (n - 2) + … + 1 (n * (n + 1))/2
• .Note. conditions can make the code faster
• If an algorithm runs in 3 (n^2) + 5n + 73 (n^2) , the runtime is O(n^2), meaning it will
never grow faster than (n^2) asymptotically()تقريبًا
Why do we calculate Time Complexity ?
• Tells you the biggest input, code can calculate (the domain)
• Since the Contest machine = 10^8 operation / second , you began to optimize your
code
• If the range of input is bigger than 10^8 you must make an O(1) code, drop any
inconstant loop
Appendices
• Loop with goto is to jump above) (فوقnot under
• goto always has an alternative which will be more readable because it makes
spaghetti code
2|Page
Time Complexity بسم هللا الرحمن الرحيم
• Binary Search ➔ It is an efficient algorithm to search for an element in a sorted
array (or list). Instead of checking each element sequentially like Linear Search, it
repeatedly divides the search range in half]
• Space Complexity: refers to the amount of memory or storage an algorithm uses to
execute, relative to the input size n. It measures the following:
o Fixed space: Memory used by variables, constants, etc.
o Dynamic space: Memory used for data structures, recursion, or temporary
computations.
o It answers the question: How much memory does this algorithm need to run?
o Its importance: Large-scale data processing: When dealing with huge
databases, logs, or streams. Memory-constrained environments: Such as
embedded systems or cloud-based microservices with strict memory limits.
Trade-offs: Understanding when to trade memory usage for faster runtime
(or vice versa)
3|Page
