What will be the time complexity of the following
algorithm:
sum = 0;
for (i=1; i<=n; i= i*2)
for (j=1; j
sum+=i*j;
A
O(n)
B
O(logn)
C
O(n2)
D
O(n log n)
উত্তরের বিবরণ
এই প্রোগ্রামের time complexity নির্ধারণ করা হয় দুইটি লুপের বৃদ্ধির হার বিশ্লেষণ করে। নিচে ধাপে ধাপে ব্যাখ্যা করা হলো।
-
Outer Loop:
for (i = 1; i <= n; i = i * 2)
এখানে i প্রতি ধাপে দ্বিগুণ হচ্ছে, অর্থাৎ 1, 2, 4, 8,… এভাবে বাড়ছে যতক্ষণ না n অতিক্রম করছে।
তাই ধাপের সংখ্যা হয় প্রায় log₂n, অর্থাৎ O(log n)। -
Inner Loop:
for (j = 1; j < n; j++)
এখানে j এক করে বাড়ছে, তাই এটি লিনিয়ার বৃদ্ধি, অর্থাৎ O(n) বার চলবে। -
মোট Iteration:
Outer loop চলে O(log n) বার, এবং প্রতিবার inner loop চলে O(n) বার।
তাই মোট সময়ের জটিলতা হবে O(n × log n)।
প্রতিটি স্টেটমেন্ট যেমন sum += i * j — এর সময় লাগে O(1)।
যদি দুইটি লুপই লিনিয়ার হতো, যেমন—
for (i = 1; i <= n; i++)
for (j = 1; j < n; j++)
তাহলে outer loop n বার এবং inner loop n বার চলত, ফলে মোট সময় হতো O(n²)।
অতএব, মূল প্রোগ্রামের time complexity = O(n log n), যা বিকল্প ঘ-এর সঙ্গে মিলে।
0
Updated: 14 hours ago
Which one is a compile time polymorphism?
Created: 17 hours ago
A
Virtual function
B
Operator overloading
C
Function overriding
D
Dynamic binding
nswer: খ)
Operator overloading
Polymorphism in C++/OOP:
Polymorphism = ability of a function or operator to behave
differently depending on context.
It can be classified into:
0
Updated: 17 hours ago
A router processes packets @1 Gbps; if 10 packets (1200 bytes each) arrive at once, queuing delay for the 10th packets (in µs) is:
Created: 1 day ago
A
96
B
86.4
C
115.2
D
120
Answer: খ)
86.4 µs
Explanation:
link rate R=1 Gbps =109 bits/s, Packet
size L=1200 bytes.
Convert packet size to bits: L=1200
bytes×8=9600 bits
Transmission time per packet:
Ttx=L/R
=9600/109 s
=9.6×10−6 s
=9.6 μs
The 10th packet waits for the 9 packets ahead of it to be transmitted, so queuing
delay = 9×Ttx=9×9.6 μs= 86.4 μs.
যদি প্রশ্নে ট্রান্সমিশনের মোট সময় অর্থাৎ
১০টা প্যাকেট ট্রান্সমিট হতে কত সময়
লাগবে তাহলে
Total transmit time: 10×9.6 μs= 96 μs
(কিন্তু এখানে চাওয়া হয়েছে ১০ম প্যাকেটের জন্য Queuing delay) তাই উত্তর হবে খ) 86.4 µs
0
Updated: 14 hours ago
Hyper-threading:
Created: 17 hours ago
A
creates multiple physical cores
B
Allows a single physical core to execute multiple threads simultaneously
C
reduces cache size
D
Only applied to GPU
Hyper-Threading (HT) হলো Intel-এর একটি Simultaneous Multithreading (SMT) প্রযুক্তি, যা একটি single physical CPU core-কে এমনভাবে কাজ করতে সক্ষম করে যেন সেটি দুটি আলাদা logical (virtual) core। এর ফলে প্রসেসর একসাথে একাধিক থ্রেড পরিচালনা করতে পারে, যা পারফরম্যান্স ও রিসোর্স ব্যবহারে দক্ষতা বাড়ায়।
-
মূল ধারণা: Hyper-Threading মূলত একটি ফিজিক্যাল কোরের রিসোর্সগুলো (যেমন রেজিস্টার ও execution unit) ভাগ করে দেয় দুটি ভার্চুয়াল থ্রেডের মধ্যে। ফলে একটি কোর একই সময়ে দুটি নির্দেশনা (instruction stream) একসাথে প্রক্রিয়া করতে পারে।
-
প্রধান সুবিধা: এটি CPU utilization বৃদ্ধি করে, idle সময় কমায় এবং multithreaded application গুলোর গতি বাড়ায়।
-
কাজের ধরন: প্রতিটি ফিজিক্যাল কোরে দুইটি থ্রেড চালু থাকে, যা অপারেটিং সিস্টেমে আলাদা লজিক্যাল প্রসেসর হিসেবে দেখা যায়।
-
সীমাবদ্ধতা: যদিও এটি throughput বাড়ায়, তবুও এটি দ্বিগুণ পারফরম্যান্স দেয় না, কারণ দুটি থ্রেড একই ফিজিক্যাল রিসোর্স ভাগ করে নেয়।
অতএব, সঠিক উত্তর হলো খ) — Allows a single physical core to execute multiple threads simultaneously, কারণ Hyper-Threading প্রযুক্তি একটি কোরকেই একাধিক থ্রেড একসাথে চালাতে সক্ষম করে।
0
Updated: 17 hours ago
