SEM :- 1-1 (R23) introduction to programming UNIT-1

SYLLABUS
1) Introduction to Programming and Problem Solving, History
of Computers,
2) Basic organization of a computer:
3) ALU,
4) input-output units,
5) memory,
6) program counter,
7) Introduction to Programming Languages,
8) Basics of a Computer ProgramAlgorithms,
9) flowcharts (Using Dia Tool),

10) pseudo code.

11.) Introduction to Compilation and Execution,

12.) Primitive Data Types,
13.) Variables, and Constants,
14.) Basic Input and Output,
15.) Operations,
16.) Type Conversion, and Casting.

web-D Page 1
SEM :- 1-1 (R23) introduction to programming UNIT-1

PART-B

1) Problem solving techniques:

2) Algorithmic approach,
3) characteristics of algorithm,
4) Problem solving strategies:
5) Top-down approach,
6) Bottom-up approach,

7.) Time and space complexities of algorithms.

web-D Page 2
SEM :- 1-1 (R23) introduction to programming UNIT-1

1.) Introduction to programming

Certainly! Let’s dive into an introduction to programming and explore the world of
problem-solving.

What is Programming?

Programming, also known as coding, is the process of creating a set of instructions that
tell a computer how to perform specific tasks. These instructions, called programs, are
written in a language that the computer can understand and execute. Think of it as giving
commands to a robot: you provide step-by-step instructions, and the computer follows
them precisely.

The purpose of programming is to solve problems and automate tasks. By creating

programs, we can instruct computers to perform a wide range of activities, from simple
calculations to complex tasks like managing databases and designing video games.

web-D Page 3
SEM :- 1-1 (R23) introduction to programming UNIT-1

How Programming Works:

1. Problem Definition:
o Clearly define the problem you want to solve and what you want the program to
achieve.
o Understand the requirements and constraints.
2. Algorithm Design:
o Develop a step-by-step procedure (algorithm) for solving the problem.
o Break down the problem into smaller subproblems.
3. Coding:
o Translate the algorithm into a programming language using a text editor or
integrated development environment (IDE).
o Write code that follows the logic of your algorithm.
4. Testing and Debugging:
o Run the program and identify any errors (bugs).
o Debug by fixing issues and ensuring correct behavior.
5. Deployment:
o Share the program with others or use it for your own purposes.
o Deploy it on servers, devices, or cloud platforms.

Benefits of Learning to Code:

1. Develop Critical Thinking and Problem-Solving Skills:

o Programming encourages logical thinking, problem decomposition, and finding
creative solutions.
o You’ll learn to break down complex problems into manageable steps.
2. Boost Creativity and Innovation:
o Coding empowers you to build your own tools and applications.
o Turn your ideas into reality by creating software.

web-D Page 4
SEM :- 1-1 (R23) introduction to programming UNIT-1

3. Increase Employability:
o The demand for skilled programmers is high across various industries.
o Learning to code enhances your career prospects.
4. Improve Communication and Collaboration Skills:
o Working with code often requires collaboration and clear communication.
o Learn to explain your solutions effectively.

Next Steps:

1. Explore programming languages like Python, Java, or C++.

2. Start writing your first code! Try simple programs that calculate sums, print messages,
or solve basic problems.
3. Dive deeper into data structures, algorithms, and software development.

History of computers

Certainly! Let’s explore the fascinating history of computers and their evolution over
time.

Early Precursors: Abacus and Napier’s Logarithms

1. The Abacus:
o The earliest known calculating device is the abacus, dating back to at least 1100 BCE.
o The abacus consists of a rectangular frame with thin parallel rods strung with beads.
o It assigns different units (weights) to each rod, allowing representation of a wide
range of numbers.
o The abacus is a digital device, representing values discretely.
o It can perform common arithmetical operations like addition, subtraction,
multiplication, and division.
o Even today, the abacus is still used, particularly in Asia.

web-D Page 5
SEM :- 1-1 (R23) introduction to programming UNIT-1

2. Napier’s Logarithms:
o In 1614, Scottish mathematician John Napier introduced logarithms.
o Logarithms simplify multiplication problems into addition problems.
o This transformation paved the way for more efficient calculations.
o Napier’s work influenced the development of the Hindu-Arabic number system and
inspired the invention of the slide rule.

The Analytical Engine and Charles Babbage

1. The Analytical Engine:

o The modern history of computers begins with the Analytical Engine, designed by
English mathematician Charles Babbage in 1837.
o The Analytical Engine was a steam-powered mechanical computer.
o It featured concepts like stored programs, memory, and conditional branching.
o Although never fully built during Babbage’s lifetime, it laid the foundation for
future computing.
2. Ada Lovelace:
o Ada Lovelace, an English mathematician, collaborated with Babbage.
o She is often credited as the world’s first computer programmer.
o Lovelace wrote detailed notes on the Analytical Engine, including an algorithm
for calculating Bernoulli numbers.

Generations of Computers:

1. First Generation (1940s-1950s):

o Vacuum tubes and punched cards.
o ENIAC (Electronic Numerical Integrator and Computer) was one of the earliest
computers.
2. Second Generation (1950s-1960s):

web-D Page 6
SEM :- 1-1 (R23) introduction to programming UNIT-1

o Transistors replaced vacuum tubes.

o IBM 1401 and UNIVAC were prominent computers.
3. Third Generation (1960s-1970s):
o Integrated circuits (ICs) and mainframes.
o IBM System/360 series.
4. Fourth Generation (1970s-1980s):
o Microprocessors and personal computers (PCs).
o Apple II, IBM PC, and Commodore 64.
5. Fifth Generation (1980s-present):
o AI, supercomputers, and mobile devices.
o Development of programming languages and the World Wide Web.

Conclusion:

The history of computers is a journey of innovation, from ancient abacuses to today’s

powerful machines. Each generation has contributed to shaping the digital world we live
in.

2.) Basic Organization Of Computers

Certainly! Let’s explore the basic organization of a computer, including its key
components:

web-D Page 7
SEM :- 1-1 (R23) introduction to programming UNIT-1

3.) ARITHMETIC LOGIC UNIT (ALU)

The Arithmetic Logic Unit (ALU) is a fundamental component of a computer’s central

processing unit (CPU). It performs arithmetic and bitwise operations on integer binary
numbers. Here are some key points about the ALU:

 Function: The ALU handles mathematical calculations (addition, subtraction,

multiplication, division) and logical comparisons (AND, OR, NOT) on binary data.
 Inputs: The ALU receives two input operands (A and B) and an operation code (opcode)
that specifies the desired operation.
 Outputs: The ALU produces a result (Y) based on the performed operation.
 Status Signals: The ALU may also have status inputs or outputs, conveying information
about previous or current operations.
 Location: You can find the ALU within the CPU, GPUs, and other computing circuits.

Remember, the ALU is at the heart of every digital computer, enabling it to perform
essential calculations! 🖥️🖥️

Central Processing Unit (CPU):

o The CPU is the heart of the computer.

o It performs all arithmetic and logical operations.
o The Arithmetic Logic Unit (ALU) within the CPU handles mathematical
calculations and logical comparisons.
o The ALU can add, subtract, multiply, divide, and perform other operations on
data.

web-D Page 8
SEM :- 1-1 (R23) introduction to programming UNIT-1

4.) Memory Subsystem:

o The memory subsystem consists of different types of memory:

 Primary Memory (RAM):
 Stores programs and data while they are being executed.
 Volatile memory (loses data when powered off).
 Accessed directly by the CPU.
 Secondary Memory (Storage Devices):
 Non-volatile memory (retains data even when powered off).
 Examples: Hard drives, solid-state drives (SSDs), optical disks
(CDs/DVDs), and USB drives.

5.) Input-Output (I/O) Units:

o Input devices allow data to enter the computer:

 Keyboard: Common for text input.
 Mouse: Used for pointing and selecting.
 Scanners, Joysticks, and other devices.
o Output devices display or provide results:
 Monitors (screens).
 Printers.
 Speakers (for audio output).

6.) Program Counter (PC):

o The program counter keeps track of the address of the next instruction to be
executed.
o It ensures that instructions are executed in the correct sequence.

web-D Page 9
SEM :- 1-1 (R23) introduction to programming UNIT-1

o When an instruction is fetched, the PC is updated to point to the next

instruction.

Control Unit (CU):

o The control unit coordinates the activities of all other components.

o It interprets instructions, manages data flow, and controls the execution of
programs.
o The CU generates control signals to manage memory, ALU, and I/O operations.

In summary, the functional units of a computer work together to process data, execute
instructions, and produce meaningful output. The CPU, memory, I/O devices, program
counter, and control unit collaborate to make computing possible! 🖥️🖥️

7.) Introduction to Programming Languages

Certainly! Let’s explore the world of programming languages and understand their
significance in the realm of software development.

What is a Programming Language?

A programming language is a formal system of notation used by programmers to

communicate with computers.

web-D Page 10
SEM :- 1-1 (R23) introduction to programming UNIT-1

It provides a way to write instructions (code) that a computer can understand and execute.
Here are some key points about programming languages:

1. Syntax and Semantics:

o Syntax: The specific rules and structure used to write code in a programming
language.
o Semantics: The meaning associated with the code constructs.
o Programming languages are defined by their syntax and semantics.
2. Features of Programming Languages:
o Data Types: Specify the type of values (e.g., numbers, strings, booleans) that can be
stored in a program.
o Variables: Named memory locations used to store values.
o Operators: Symbols for performing operations (e.g., addition, subtraction,
comparison).
o Control Structures: Statements for controlling program flow (e.g., if-else, loops).
o Libraries and Frameworks: Pre-written code collections for common tasks.
o Paradigms: Different programming styles (e.g., procedural, object-oriented,
functional).
3. Popular Programming Languages:
o Python: Known for its readability and versatility.
o Java: Widely used for web applications, Android apps, and enterprise systems.
o C++: Used for system-level programming and game development.
o JavaScript: Essential for web development (runs in browsers).
o Ruby, C#, and many others.
4. Choosing a Language:
o The choice of programming language depends on:
 Project requirements (e.g., web development, data science, mobile apps).
 Platform (desktop, web, mobile).
 Audience (developers, end-users).
 Desired outcome.

web-D Page 11
SEM :- 1-1 (R23) introduction to programming UNIT-1

Conclusion:

Programming languages empower developers to create software, automate tasks, and

build innovative solutions. Whether you’re a beginner or an experienced coder,
understanding programming languages is essential for your journey in the world of
technology! 🖥️🖥️🖥️

8.) Algorithms:

 An algorithm is a step-by-step procedure or set of rules for solving a specific problem.

 It provides a clear and unambiguous description of how to perform a task.
 Algorithms can be expressed in natural language, pseudocode, or programming
languages.

9.) Flowcharts:

 A flowchart is a graphical representation of an algorithm or process.

 It uses symbols connected by arrows to indicate the flow of information and processing
steps.

web-D Page 12
SEM :- 1-1 (R23) introduction to programming UNIT-1

 Common flowchart symbols:

o Terminal (Start/Stop): Represents the beginning or end of a process.
o Input/Output: Indicates input from or output to external sources.
o Process: Represents an action or operation (e.g., calculations).
o Decision: Represents a choice or condition (e.g., if-else).
o Connector: Connects different parts of a flowchart.
 Example: Drawing a flowchart to input two numbers from the user and display the
largest of the two.

10.) Pseudo Code:

 Pseudocode is an informal high-level description of an algorithm.

 It combines elements of natural language and programming constructs.

web-D Page 13
SEM :- 1-1 (R23) introduction to programming UNIT-1

 Pseudocode helps programmers plan and design their code before writing it in a specific
programming language.

11.) Compilation and Execution:

1. Compilation:
o The process of converting human-readable source code (written in a
programming language) into machine-readable code (binary or bytecode).
o A compiler translates the entire program at once.
o Common compiled languages: C, C++, Java (to bytecode).
2. Execution:
o After compilation, the program can be executed by the computer.
o The operating system loads the compiled binary or bytecode into memory.
o The CPU executes the instructions sequentially.

web-D Page 14
SEM :- 1-1 (R23) introduction to programming UNIT-1

12.) Primitive Data Types in C:

1. Integer (int):
o Represents whole numbers (positive, negative, or zero).
o Examples: 42, -10, 0.
o Syntax for declaring an integer variable:
o int myNumber;
2. Floating Point (float):
o Represents numbers with decimal points.
o Examples: 3.14, -0.005, 123.456.
o Syntax for declaring a floating-point variable:
o float myFloat;
3. Character (char):
o Represents a single character (letter, digit, punctuation mark, or symbol).
o Enclosed in single quotes (' ').
o Examples: 'A', '7', '%'.
o Syntax for declaring a character variable:
o char myChar;
4. Constants:
o Constants are fixed values that do not change during program execution.
o Examples:
 Integer constant: const int DAYS_IN_WEEK = 7;
 Floating-point constant: const float PI = 3.14159;
 Character constant: const char NEWLINE = '\n';

13.) Variables and Basic Input/Output:

1. Variables:
o A variable is a named memory location used to store data.
o Syntax for declaring and initializing a variable:

web-D Page 15
SEM :- 1-1 (R23) introduction to programming UNIT-1

o int age = 25;

o float price = 9.99;
o char grade = 'A';
2. Input/Output:
o To read input from the user:
o scanf("%d", &age); // Read an integer
o To display output:
o printf("Your age is %d\n", age);

14.) Type Conversion and Casting:

1. Implicit Type Conversion:

o Automatic conversion between data types.
o Example:
o int num1 = 10;
o float num2 = num1; // Implicitly converts int to float
2. Explicit Type Conversion (Casting):
o Manually specify the desired type.
o Syntax: (target_type) expression
o Example:
o float pi = 3.14159;
o int approxPi = (int) pi; // Casts float to int

15.) Operators
Certainly! Let’s explore the various operations available in the C programming
language. We’ll cover arithmetic, relational, logical, assignment, and other operators.

Arithmetic Operators:

1. Addition (+):

web-D Page 16
SEM :- 1-1 (R23) introduction to programming UNIT-1

o Adds two values.

o Example: int sum = 10 + 5;
2. Subtraction (-):
o Subtracts one value from another.
o Example: int difference = 20 - 8;
3. Multiplication (*):
o Multiplies two values.
o Example: int product = 6 * 4;
4. Division (/):
o Divides one value by another.
o Example: float quotient = 15.0 / 3;
5. Modulus (%):
o Computes the remainder after division.
o Example: int remainder = 17 % 5;

Relational Operators:

1. Less Than (<):

o Returns true if the left operand is less than the right operand.
o Example: int result = 7 < 10; // true
2. Greater Than (>):
o Returns true if the left operand is greater than the right operand.
o Example: int result = 15 > 12; // true
3. Less Than or Equal To (<=):
o Returns true if the left operand is less than or equal to the right operand.
o Example: int result = 5 <= 5; // true
4. Greater Than or Equal To (>=):
o Returns true if the left operand is greater than or equal to the right operand.
o Example: int result = 20 >= 18; // true

web-D Page 17
SEM :- 1-1 (R23) introduction to programming UNIT-1

Logical Operators:

1. Logical AND (&&):

o Returns true if both operands are true.
o Example: int result = (5 > 3) && (10 < 15); // true
2. Logical OR (||):
o Returns true if at least one operand is true.
o Example: int result = (7 == 7) || (12 != 10); // true
3. Logical NOT (!):
o Inverts the truth value of an expression.
o Example: int result = !(3 > 5); // true

Assignment Operators:

1. Assignment (=):
o Assigns a value to a variable.
o Example: int x = 42;
2. Compound Assignment (+=, -=):
o Performs an operation and assigns the result to a variable.
o Example: x += 10; // Equivalent to x = x + 10;

Bitwise Operators:

1. Bitwise AND (&):

o Performs a bitwise AND operation on corresponding bits of two integers.
o Example: int result = 5 & 3; // Binary: 0101 & 0011 = 0001
2. Bitwise OR (|):
o Performs a bitwise OR operation on corresponding bits of two integers.
o Example: int result = 5 | 3; // Binary: 0101 | 0011 = 0111

web-D Page 18
SEM :- 1-1 (R23) introduction to programming UNIT-1

3. Bitwise XOR (^):

o Performs a bitwise XOR (exclusive OR) operation on corresponding bits of
two integers.
o Example: int result = 5 ^ 3; // Binary: 0101 ^ 0011 = 0110
4. Bitwise NOT (~):
o Inverts all the bits of an integer.
o Example: int result = ~5; // Binary: ~0101 = 1010

Shift Operators:

1. Left Shift (<<):

o Shifts the bits of an integer to the left by a specified number of positions.
o Example: int result = 10 << 2; // Binary: 1010 << 2 = 101000
2. Right Shift (>>):
o Shifts the bits of an integer to the right by a specified number of positions.
o Example: int result = 15 >> 2; // Binary: 1111 >> 2 = 0011

Order of Precedence:

 Operators have different priorities. Use parentheses to control the order of

evaluation.
 Example: int result = (5 + 3) * 2; // Parentheses first, then
multiplication

Other Operators:

1. Ternary Operator (?:):

o Also known as the conditional operator.
o Provides a shorthand for an if-else statement.
o Syntax: condition ? expression1 : expression2

web-D Page 19
SEM :- 1-1 (R23) introduction to programming UNIT-1

o Example:
o int max = (a > b) ? a : b;
2. Comma Operator (``,`):
o Evaluates multiple expressions sequentially and returns the value of the last
expression.
o Often used in for loops or function calls.
o Example:
o int x = 10, y = 20;
o int sum = (x += 5, y += 3); // sum = 23
3. sizeof Operator:
o Determines the size (in bytes) of a data type or variable.
o Example:
o int sizeInt = sizeof(int); // sizeInt = 4 (on most systems)
4. Address-of Operator (&):
o Returns the memory address of a variable.
o Used for pointers and passing arguments by reference.
o Example:
o int num = 42;
o int* ptr = &num; // ptr now holds the address of num
5. Pointer Dereference Operator (*):
o Accesses the value stored at a memory address pointed to by a pointer.
o Example:
o int value = *ptr; // Retrieves the value stored at the
address pointed by ptr

These operators are essential for more advanced C programming tasks. Remember to
practice and explore their usage!

web-D Page 20
SEM :- 1-1 (R23) introduction to programming UNIT-1

C Programs for Arithmetic Operators:

Addition, Subtraction, Multiplication, Division, and Modulus:

#include <stdio.h>
int main() {
int num1, num2;
printf("Enter any two numbers: ");
scanf("%d %d", &num1, &num2);
printf("Sum = %d\n", num1 + num2);
printf("Difference = %d\n", num1 - num2);
printf("Product = %d\n", num1 * num2);
printf("Quotient = %.2f\n", (float)num1 / num2);
printf("Modulus = %d\n", num1 % num2);
return 0;
}

Increment and Decrement:

#include <stdio.h>
int main() {
int a = 5;
printf("Initial value of a: %d\n", a);
printf("After increment: %d\n", ++a);
printf("After decrement: %d\n", --a);
return 0;
}

web-D Page 21
SEM :- 1-1 (R23) introduction to programming UNIT-1

Part-B

1.) Problem Solving Through Programming in C:

1. Understanding the Problem:

o Before diving into code, thoroughly understand the problem you need to solve.
o Define the problem’s objectives and requirements.
2. Analyzing the Problem:
o Break down the problem into smaller components.
o Identify patterns, constraints, and potential challenges.
3. Developing the Solution:
o Design an algorithm (step-by-step plan) to solve the problem.
o Use tools like flowcharts, pseudocode, or plain English descriptions.
4. Coding and Implementation:
o Translate your algorithm into C code.
o Write functions, loops, conditionals, and other constructs.

General Problem-Solving Strategies:

1. Divide and Conquer:

o Break a complex problem into smaller subproblems.
o Solve each subproblem independently and combine the results.
2. Binary Doubling:
o Efficiently compute powers of a number using binary representation.
3. Dynamic Programming:
o Solve problems by breaking them into overlapping subproblems.
o Store intermediate results to avoid redundant calculations.
4. General Search, Backtracking, and Branch-and-Bound:
o Explore solution spaces systematically.

web-D Page 22
SEM :- 1-1 (R23) introduction to programming UNIT-1

o Backtrack when necessary to explore alternative paths.

Remember that problem-solving skills are crucial for becoming a proficient programmer.
Practice, analyze, and refine your approach! 🖥️🖥️🖥️

2.) What is an Algorithm?

An algorithm is a systematic approach or step-by-step procedure for solving a specific

problem. It provides a clear and unambiguous set of rules or instructions to achieve a
desired outcome. Here are some key points about algorithms:

1. Well-Described Steps:
o Algorithms consist of specific and finite steps that can be followed to perform a
particular task.
o Each step should be well-defined, leaving no room for ambiguity or confusion.
2. Language-Independent:
o Algorithms are language-independent. They can be implemented in any
programming language, and the output remains consistent.
o They represent the logic or plan for solving a problem, regardless of the chosen
language.
3. Applications of Algorithms:
o Algorithms play a crucial role in various fields:

web-D Page 23
SEM :- 1-1 (R23) introduction to programming UNIT-1

 Computer Science: Algorithms form the basis of computer programming,

from simple sorting and searching to complex tasks like artificial intelligence
and machine learning.
 Mathematics: Algorithms solve mathematical problems, such as finding
optimal solutions or shortest paths.
 Operations Research: Algorithms optimize processes in transportation,
logistics, and resource allocation.
 Artificial Intelligence: Algorithms underpin intelligent systems for tasks like
image recognition and natural language processing.
 Data Science: Algorithms analyze and extract insights from large datasets.

3.) Characteristics of an Algorithm:

1. Finiteness:
o An algorithm must terminate after a finite number of steps.
o It cannot run indefinitely.
2. Definiteness:
o Each step of the algorithm must be precisely defined.
o There should be no ambiguity or guesswork.
3. Input:
o An algorithm takes input (if required) to produce an output.
o Inputs can be data, parameters, or initial conditions.
4. Output:
o An algorithm produces a result or output based on the given input.
o The output should be relevant to the problem being solved.
5. Effectiveness:
o An algorithm must be practical and feasible to execute.
o It should not require infinite resources or time.

web-D Page 24
SEM :- 1-1 (R23) introduction to programming UNIT-1

Certainly! Let’s explore some example algorithms in both C. These algorithms

demonstrate common problem-solving techniques.

Algorithm to Add Two Numbers:

C Implementation:
#include <stdio.h>

int main() {
int num1, num2;
printf("Enter two numbers: ");
scanf("%d %d", &num1, &num2);
int sum = num1 + num2;
printf("Sum = %d\n", sum);
return 0;
}

Algorithm to Find the Largest Among Three Numbers:

C Implementation:
#include <stdio.h>

int main() {
int a, b, c;
printf("Enter three numbers: ");
scanf("%d %d %d", &a, &b, &c);
if (a >= b && a >= c)
printf("%d is the largest number.\n", a);
else if (b >= c)
printf("%d is the largest number.\n", b);
else
printf("%d is the largest number.\n", c);
return 0;
}

web-D Page 25
SEM :- 1-1 (R23) introduction to programming UNIT-1

4.) PROBLEM SOLVING STRATEGIES

Certainly! Let’s explore the top-down approach and the bottom-up approach in
problem-solving and system development.

Top-Down Approach:

1. Definition:
o In the top-down approach, you start with an overview of the entire system or
problem.
o You formulate a high-level vision and then break it down into smaller components.
o Decision-making occurs at the highest level and is communicated to lower levels.
2. How It Works:
o Higher-level decision-makers begin with a big picture goal.
o They work backward to determine what actions different groups and individuals
need to take to achieve that goal.
o The entire project planning process takes place at the management level.
o Once an action plan is created, it is communicated to the rest of the team for
implementation.
o

web-D Page 26
SEM :- 1-1 (R23) introduction to programming UNIT-1

3. Advantages:
o Eliminates confusion and reduces risk.
o Keeps initiatives organized across larger teams.
o Well-practiced process that grows more efficient over time.
4. Use Cases:
o Traditional industries (e.g., retail, healthcare, manufacturing) often apply the top-
down management style.
o Legacy organizations (e.g., IBM, The New York Times) operate their entire companies
using this approach.

Bottom-Up Approach:

1. Definition:
o In the bottom-up approach, individual parts of the system are specified in detail.
o These parts are then linked to form larger components, which are further linked
until a complete system is formed.
2. How It Works:
o Smaller problems are solved individually.
o Integration occurs to create a whole and complete solution.
o Object-oriented languages (e.g., C++, Java) often use a bottom-up approach.
3. Advantage:
o Minimizes redundancy by using data encapsulation and data hiding.
o Allows communication among modules.
4. Use Cases:
o Testing and debugging.
o Suited for defects occurring at the bottom of the program.

Remember that both approaches have their merits, and the choice depends on the specific
problem and context!

web-D Page 27
SEM :- 1-1 (R23) introduction to programming UNIT-1

5.) Time Complexity:

 Time complexity quantifies the amount of time taken by an algorithm to run as a

function of the length of the input.
 It measures how the execution time grows as the input size increases.
 Notation: Big O notation (O).
 Common time complexities:
o Constant Time (O(1)): The algorithm’s runtime remains constant regardless of
the input size. Example: accessing an element in an array by index.
o Linear Time (O(n)): The algorithm’s runtime grows linearly with the input size.
Example: iterating through an array.
o Quadratic Time (O(n^2)): The algorithm’s runtime grows quadratically with the
input size. Example: nested loops.
o Logarithmic Time (O(log n)): Common in divide-and-conquer algorithms.
Example: binary search.
o Linearithmic Time (O(n log n)): Common in efficient sorting algorithms like
merge sort and quicksort.

Space Complexity:

 Space complexity quantifies the amount of memory or space required by an algorithm

to run as a function of the input size.
 It measures how the memory usage grows as the input size increases.
 Notation: Big O notation (O).
 Common space complexities:
o Constant Space (O(1)): The algorithm uses a fixed amount of memory regardless
of the input size.
o Linear Space (O(n)): The memory usage grows linearly with the input size.

web-D Page 28
SEM :- 1-1 (R23) introduction to programming UNIT-1

o Quadratic Space (O(n^2)): The memory usage grows quadratically with the input
size.
o Logarithmic Space (O(log n)): Common in recursive algorithms with balanced
trees.

Remember that analyzing time and space complexities helps us choose efficient
algorithms for solving problems!

web-D Page 29