TCYS133 Algorithm and Data Structure
Tutorial 2
Name: YONG KAI XIONG
Student ID: 2490123DCS
1. Define algorithm analysis and explain why analyzing algorithms is important.
Algorithm analysis is the process of predicting the resources an algorithm requires, such
as memory, communication bandwidth, and computational time. It is important because it
can help us choose the most efficient algorithm when there are multiple options for the
same problem. Besides, it also allows us to predict the resource requirements of an
algorithm, with a primary focus on computation time. Which it helps determine if an
algorithm is optimal or if a better one might be possible.
2. Differentiate between time complexity and space complexity.
Time Complexity which is measures the amount of time an algorithm takes to run as a
function of the input size. It tells how long the algorithm will take to complete its task.
While Space Complexity measures the amount of memory an algorithm requires in
relation to the input size. Which it includes both the memory needed for the input itself
and any extra memory the algorithm uses. In conclusion, time complexity is related to
time taken and space complexity is related to memory that required.
3. Explain the meaning and importance of Big O notation in algorithm design.
Big O notation is a mathematical tool used to describe the upper bound of an algorithm's
time or space complexity. It provides a standardized way to quantify how efficient an
algorithm is, ignoring constant factors and lower-order terms to focus on the dominant,
fastest-growing term. The Big O notation is important because it allows developers to
compare the efficiency of different algorithms in a standardized way. This will help
developer to identify and optimize the most resource-intensive parts of code, ensuring
that software can scale to handle large inputs without a major loss in performance. In
conclusion, Big O notation is important by help us in making informed decisions about
algorithm selection and optimization.
TCYS133 Algorithm and Data Structure
4. Explain the concept of algorithm efficiency and discuss how time complexity,
space complexity, and Big O notation are used to evaluate the performance of
algorithms.
Algorithmic efficiency is determined by an algorithm's time and space complexity, which
directly affects its scalability and ability to handle large inputs. An efficient algorithm is
one that can process data quickly while using minimal memory. Time and Space
Complexity are the core metrics. Time complexity measures how long an algorithm takes
to run, while space complexity measures the memory it needs. While Big O Notation is
used to express these complexities. It describes the growth rate of an algorithm's time or
space requirements as the input size increases. By using Big O, developers can compare
different algorithms to determine which is more efficient and scalable for a given task.
5. Define asymptotic analysis and explain its purpose in evaluating algorithms.
Asymptotic analysis is the study of how an algorithm's performance scales as the size of
its input approaches infinity. It focuses on the dominant term of the algorithm's
complexity, which ultimately determines its overall efficiency for large inputs. Its main
purpose in evaluating algorithms is to provide a powerful tool for comparing and
selecting the most appropriate algorithms for a given problem. By understanding the
growth rate of an algorithm's complexity, developers can choose the most efficient
solution that can effectively handle the expected input size.
6. Processing E-Commerce Orders Scenario:
An e-commerce company processes thousands of customer orders daily.
The system must check each order’s payment status before confirming shipment.
Two methods are considered:
Method A: Scan all records one by one each time a new order is placed.
Method B: Store records in a binary search tree for faster lookup.
a) Compare the time complexity of both methods.
Method Operation Time Complexity
Method A (Linear Checks each order one by one until it O(n)
Scan) finds the correct payment record.
Method B (Binary Searches efficiently using comparisons O(log n) for a
Search Tree) in a tree structure. balanced BST
TCYS133 Algorithm and Data Structure
b) Explain how input size (number of orders) impacts the performance of each
method.
For Method A (O(n)), as the number of orders increases, the time to check each payment
grows linearly. While for Method B (O(log n)), as the number of orders increases, the
time increases very slowly.
c) Discuss which method is more scalable and why.
Method B is more scalable because it handles larger datasets efficiently. The logarithmic
growth in time complexity means performance won’t degrade rapidly even as the
business grows and handles millions of orders. Method B is more scalable because its
O(log n) complexity allows it to perform well even with a large number of orders.
Method A becomes impractical at large scale due to linear growth in processing time.
d) What factors other than time complexity (e.g., memory usage, implementation
difficulty) might influence the choice?
Factor Explanation
Memory Usage BSTs use more memory to store pointers and tree structure,
while scanning only needs a simple list.
Implementation Scanning is easy to implement; BST requires more
Difficulty programming and maintenance (especially balancing).
Insertion/Deletion BST handles insertions and deletions efficiently; scanning
Frequency would require more time.
Hardware Resources If memory or computing power is limited, simpler methods
may be preferred.
Data Access Patterns If lookups are frequent, BST is better; if only occasional,
linear scan may be sufficient.
e) How does Big O notation help the company predict system performance as the
number of orders grows?
Big O notation helps the company predict performance by providing a standardized way
to understand how each method scales with the input size (number of orders). It allows
them to see that Method A's performance will degrade linearly as orders increase, while
Method B's performance will remain very high. This helps them choose the algorithm
that can handle future growth effectively.
TCYS133 Algorithm and Data Structure
7. You are asked to design two algorithms to find the maximum number in a list:
Algorithm A scans the entire list once.
Algorithm B sorts the list first, then picks the last element.
Compare their time complexity using Big O notation and explain which one is more
efficient and why.
Algorithm Steps Time Complexity
Algorithm Traverse each element once O(n)
A and keep track of the largest.
Algorithm Sorts the list then takes the last O(n log n) (for sorting) + O(1) (for
B element. picking last) → O(n log n) total.
Algorithm A is more efficient. An algorithm with O(n) time complexity has a slower
growth rate than one with O(n log n) complexity. This means that as the list of numbers
gets larger, the single scan in Algorithm A will be significantly faster than sorting the
entire list in Algorithm B.