Real-world modeling in C++ - Time & Space Complexity

Time Complexity: Real-world modeling

O(n²)

Understanding Time Complexity

When we model real-world problems in code, we want to know how long our program takes as the problem grows.

We ask: How does the work increase when the input gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

#include <vector>
#include <iostream>

void printPairs(const std::vector<int>& nums) {
    for (int i = 0; i < nums.size(); ++i) {
        for (int j = 0; j < nums.size(); ++j) {
            std::cout << nums[i] << "," << nums[j] << std::endl;
        }
    }
}
    

This code prints all pairs of numbers from the input list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops printing pairs of elements.
• How many times: Outer loop runs n times; inner loop runs n times for each outer loop.

How Execution Grows With Input

As the input size grows, the number of pairs grows much faster.

Input Size (n)	Approx. Operations
10	100
100	10,000
1000	1,000,000

Pattern observation: Doubling the input size makes the work about four times bigger.

Final Time Complexity

Time Complexity: O(n²)

This means the work grows by the square of the input size; twice the input means about four times the work.

Common Mistake

[X] Wrong: "Since there are two loops, the time is just twice as long as input size."

[OK] Correct: The loops are nested, so the inner loop runs fully for each outer loop step, multiplying the work, not adding.

Interview Connect

Understanding how nested loops affect time helps you explain your code clearly and shows you can think about efficiency in real problems.

Self-Check

"What if we changed the inner loop to run only from j = i to the end? How would the time complexity change?"

Practice

1. What is the main purpose of using classes in real-world modeling in C++?

easy

A. To write faster code without any structure

B. To represent real-world objects with attributes and behaviors

C. To avoid using variables in the program

D. To make the program run without errors

Solution

1. Step 1: Understand the role of classes

   Classes group data (attributes) and functions (methods) to model real-world things.

2. Step 2: Identify the purpose in modeling

   Classes help represent objects with their properties and actions clearly.

3. Final Answer:

   To represent real-world objects with attributes and behaviors -> Option B

4. Quick Check:

   Classes model objects = A [OK]

Hint: Classes group data and actions like real objects [OK]

Common Mistakes:

• Thinking classes only speed up code
• Confusing classes with simple variables
• Believing classes remove all errors

2. Which of the following is the correct way to declare a class named Car in C++?

easy

A. Car class { };

B. class = Car { };

C. class Car { };

D. class Car();

Solution

1. Step 1: Recall C++ class syntax

   The correct syntax starts with the keyword class, followed by the class name and braces.

2. Step 2: Check each option

   class Car { }; uses class Car { }; which is correct. Others have syntax errors.

3. Final Answer:

   class Car { }; -> Option C

4. Quick Check:

   Correct class syntax = B [OK]

Hint: Use 'class Name { };' to declare classes [OK]

Common Mistakes:

• Writing 'Car class' instead of 'class Car'
• Using parentheses after class name
• Missing semicolon after class definition

3. What will be the output of this C++ code?

class Dog {
public:
  int age;
  void bark() { std::cout << "Woof!"; }
};

int main() {
  Dog myDog;
  myDog.age = 5;
  std::cout << myDog.age << " ";
  myDog.bark();
  return 0;
}

medium

A. Woof!5

B. Woof! 5

C. 5Woof!

D. 5 Woof!

Solution

1. Step 1: Analyze output statements

   The code prints myDog.age followed by a space, then calls bark() which prints "Woof!".

2. Step 2: Combine outputs

   Output is 5 plus Woof!, so result is "5 Woof!".

3. Final Answer:

   5 Woof! -> Option D

4. Quick Check:

   Print age + space + bark = 5 Woof! [OK]

Hint: Check order and spaces in output statements [OK]

Common Mistakes:

• Assuming space after bark output
• Mixing order of printed values
• Ignoring no newline after prints

4. Identify the error in this C++ class definition:

class Book {
  string title;
  int pages;
public:
  void setTitle(string t) { title = t; }
  void setPages(int p) { pages = p; }
};

medium

A. Missing std:: before string

B. Missing semicolon after class definition

C. Methods should be declared outside the class

D. Private members must be declared after public

Solution

1. Step 1: Check usage of string type

   The code uses string without std:: or using namespace std;.

2. Step 2: Identify missing namespace

   In C++, string is in the std namespace, so std::string is needed unless using directive is present.

3. Final Answer:

   Missing std:: before string -> Option A

4. Quick Check:

   Use std::string or using namespace std [OK]

Hint: Always prefix string with std:: or use namespace std [OK]

Common Mistakes:

• Forgetting std:: prefix for string
• Thinking methods must be outside class
• Believing private must come after public

5. You want to model a Library that holds many Book objects. Which design best represents this real-world relationship in C++?

hard

A. class Library { std::vector<Book> books; };

B. class Library { Book book; };

C. class Library { int bookCount; };

D. class Library { void addBook(Book b); };

Solution

1. Step 1: Understand the relationship

   A library contains many books, so it needs a collection (like a vector) of Book objects.

2. Step 2: Evaluate options

   class Library { std::vector<Book> books; }; uses std::vector<Book> to hold multiple books, matching the real-world model.

3. Final Answer:

   class Library { std::vector<Book> books; }; -> Option A

4. Quick Check:

   Use collection for many objects = D [OK]

Hint: Use vector to hold many objects in a class [OK]

Common Mistakes:

• Using single object instead of collection
• Only storing count without objects
• Defining methods without data members