JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD MCA 2022 DATA STRUCTURES AND ALGORITHMS Previous Question Paper (October/November - 2022 - R15)

Asymptotic notations are mathematical tools used to describe the limiting behavior of a function, typically representing the time or space complexity of an algorithm.

i) Big O notation (O): Provides an asymptotic upper bound on the growth rate of a function. It represents the worst-case scenario. Formally, f(n) = O(g(n)) if there exist positive constants c and n0 such that 0 ≤ f(n) ≤ c·g(n) for all n ≥ n0.

ii) Omega notation (Ω): Provides an asymptotic lower bound on the growth rate of a function. It represents the best-case scenario. Formally, f(n) = Ω(g(n)) if there exist positive constants c and n0 such that 0 ≤ c·g(n) ≤ f(n) for all n ≥ n0.

iii) Theta notation (Θ): Provides an asymptotic tight bound on the growth rate of a function. It represents the average or exact growth rate. Formally, f(n) = Θ(g(n)) if there exist positive constants c1, c2, and n0 such that c1·g(n) ≤ f(n) ≤ c2·g(n) for all n ≥ n0.

A stack is a Last-In-First-Out (LIFO) data structure. The following C implementation uses an array to perform push, pop, and peek operations.

#include <stdio.h>
#define MAX 100

int stack[MAX], top = -1;

void push(int val) {
    if (top == MAX - 1) printf("Stack Overflow\n");
    else stack[++top] = val;
}

int pop() {
    if (top == -1) { printf("Stack Underflow\n"); return -1; }
    return stack[top--];
}

void display() {
    for(int i = top; i >= 0; i--) printf("%d ", stack[i]);
    printf("\n");
}

int main() {
    push(10); push(20);
    display();
    printf("Popped: %d\n", pop());
    return 0;
}