[go: up one dir, main page]
Scribd
Upload
14 views2 pages

Time Complexity

The document provides an introduction to algorithms, defining them as step-by-step procedures for problem-solving. It explains time complexity, which measures the time an algorithm takes based on input size, and space complexity, which measures memory usage. Additionally, it outlines key notations for complexity analysis and recommends study materials for further learning.

Uploaded by

Rithan Dsouza
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
14 views2 pages

Time Complexity

The document provides an introduction to algorithms, defining them as step-by-step procedures for problem-solving. It explains time complexity, which measures the time an algorithm takes based on input size, and space complexity, which measures memory usage. Additionally, it outlines key notations for complexity analysis and recommends study materials for further learning.

Uploaded by

Rithan Dsouza
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Introduction to Algorithms

(with Time Complexity and Space Complexity)

What is an Algorithm?

An algorithm is a step-by-step, finite procedure for solving a problem or performing a computation.

 Example: Sorting numbers in an array, searching for an item in a list.

Time Complexity

 Definition: Measures the amount of time an algorithm takes as a function of the input size
(commonly denoted as n).

 Useful for comparing algorithm performance, independent of programming language and hardware.

Notations

 Big O (𝑂): Worst-case scenario (upper bound).

 Omega (Ω): Best-case scenario (lower bound).

 Theta (Θ): Average or tight bound.

Example

for i in range(n):
print(i)

 This loop runs 𝑛 times → Time complexity is 𝑂(𝑛) (linear time).

Space Complexity

 Definition: Measures the total memory used by an algorithm, proportional to input size.

Includes:

 Fixed space: Variables, constants

 Variable space: Dynamically allocated structures, recursion stack


Example

arr = [0] * n

 Creates an array of size 𝑛 → Space complexity is 𝑂(𝑛).

Key Differences

Complexity What it Measures Example Notation

Time Complexity Speed (how fast) 𝑂(𝑛), 𝑂(𝑛 )

Space Complexity Memory usage (how much RAM) 𝑂(1), 𝑂(𝑛)

Study Material Recommendations

 GeeksforGeeks – Time and Space Complexity Tutorial

 HackerEarth – Complexity Analysis basics

 PDFs & digital lecture notes available online for DOA topics

You might also like